如何在（Python）列表中用顺序替换数字

Question

我有一个包含整数的列表，想要替换它们，使先前包含最高数字的元素现在包含1，第二高的数字设置为2，以此类推。

例如：[5, 6, 34, 1, 9, 3] 应该得到 [4, 3, 1, 6, 2, 5]。

我只关心前9个最高的数字，但我认为可能有一个简单的算法或甚至是一个Python函数来处理这个任务？

编辑：我不关心如何处理重复项。

- Max Matti

---

请提供您尝试的代码片段。 - Mayank

如果两个数字相同怎么办？ - Willem Van Onsem

我想到了这个代码：tmp = sorted(input); output = [0] * len(input); for i in range(min(len(tmp), 9)): output[input.index(tmp[i])] = i，但我还没有测试过。此外，这段代码对重复项的处理不太好。 - Max Matti

Answer 1

一种快速的方法是先生成一个元素及其位置的元组列表：

sort_data = [(x,i) for i,x in enumerate(data)]

接下来，我们将这些元素按照相反的顺序排序：

sort_data = sorted(sort_data,reverse=True)

生成（对于您的示例输入）：

>>> sort_data
[(34, 2), (9, 4), (6, 1), (5, 0), (3, 5), (1, 3)]

接下来，我们需要填写这些元素，例如：

result = [0]*len(data)
for i,(_,idx) in enumerate(sort_data,1):
    result[idx] = i

或者把它放在一起：

def obtain_rank(data):
    sort_data = [(x,i) for i,x in enumerate(data)]
    sort_data = sorted(sort_data,reverse=True)
    result = [0]*len(data)
    for i,(_,idx) in enumerate(sort_data,1):
        result[idx] = i
    return result

这种方法在data元素个数为n时以O(n log n)的时间复杂度运行。

一种更紧凑的算法（意味着不需要为排序构造元组）是：

def obtain_rank(data):
    sort_data = sorted(<b>range(len(data)),key=lambda i:data[i]</b>,reverse=True)
    result = [0]*len(data)
    for i,<b>idx</b> in enumerate(sort_data,1):
        result[idx] = i
    return result

- Willem Van Onsem

---

@Rawing：它用于存储元素的原始位置。Ev.Kounis算法更优雅，但运行时间为*O(n^2 log n)，而这个算法的运行时间为O(n log n)*。 - Willem Van Onsem

Answer 2

另一个选项是使用 scipy 的 rankdata 函数，它提供了处理重复值的选项：

from scipy.stats import rankdata

lst = [5, 6, 34, 1, 9, 3]
rankdata(list(map(lambda x: -x, lst)), method='ordinal')
# array([4, 3, 1, 6, 2, 5])

- Psidom

Answer 3

假设您没有任何重复项，以下列表综合将起作用：

lst = [5, 6, 34, 1, 9, 3]
tmp_sorted = sorted(lst, reverse=True)  # kudos to @Wondercricket
res = [tmp_sorted.index(x) + 1 for x in lst]  # [4, 3, 1, 6, 2, 5]

为了理解它的工作原理，您可以将其分解成以下几个部分：

lst = [5, 6, 34, 1, 9, 3]
# let's see what the sorted returns
print(sorted(lst, reverse=True))  # [34, 9, 6, 5, 3, 1]
# biggest to smallest. that is handy.
# Since it returns a list, i can index it. Let's try with 6
print(sorted(lst, reverse=True).index(6))  # 2
# oh, python is 0-index, let's add 1
print(sorted(lst, reverse=True).index(6) + 1)  # 3
# that's more like it. now the same for all elements of original list

for x in lst:
    print(sorted(lst, reverse=True).index(x) + 1)  # 4, 3, 1, 6, 2, 5

# too verbose and not a list yet..
res = [sorted(lst, reverse=True).index(x) + 1 for x in lst]
# but now we are sorting in every iteration... let's store the sorted one instead
tmp_sorted = sorted(lst, reverse=True)
res = [tmp_sorted.index(x) + 1 for x in lst]

- Ma0

---

最好在列表推导式之前对列表进行排序。目前的情况是在每次迭代中通过对lst进行排序来完成。repl.it 演示了这种方法的性能差异。 - Wondercricket

此外，index(..) 的时间复杂度是 *O(n)*，使得这个算法的时间复杂度为 *O(n^2 log n)*。 - Willem Van Onsem

@WillemVanOnsem 我不太擅长计算复杂度。你是怎么推导出来的？如果“index”在O(n)中运行，那它不就是O(n^2)吗？ - Ma0

@Ev.Kounis：现在它确实以*O(n^2)的时间运行（因为排序步骤只执行一次）。由于index在O(n)的时间内运行，并且您这样做了O(n)*次。 - Willem Van Onsem

@WillemVanOnsem 哦，我明白了。谢谢。 - Ma0

好的，那个解释比我需要的详细多了，但还是谢谢！ - Max Matti

Answer 4

使用 numpy.argsort：

numpy.argsort 返回一个数组排序后的索引。

---

>>> xs = [5, 6, 34, 1, 9, 3]

>>> import numpy as np
>>> np.argsort(np.argsort(-np.array(xs))) + 1
array([4, 3, 1, 6, 2, 5])

- falsetru

---

我不确定我理解这个，-np.array()是什么意思，为什么要加1？ - nycynik

np.array(xs) 创建一个numpy数组。-np.array(xs) 返回一个新的数组，其中所有项都被取反。 - falsetru

Answer 5

一个使用纯Python和无查找表的短小的对数线性解决方案。

思路：将位置存储在一对列表中，然后对列表进行排序以重新排列位置。

enum1 = lambda seq: enumerate(seq, start=1)  # We want 1-based positions

def replaceWithRank(xs):
    # pos = position in the original list, rank = position in the top-down sorted list.
    vp = sorted([(value, pos) for (pos, value) in enum1(xs)], reverse=True)
    pr = sorted([(pos, rank) for (rank, (_, pos)) in enum1(vp)])
    return [rank for (_, rank) in pr]

assert replaceWithRank([5, 6, 34, 1, 9, 3]) == [4, 3, 1, 6, 2, 5]

- 9000