如何高效获取列表中前三大值的索引？

嵌套循环的时间复杂度是O(n²)，当列表元素数量较多时效率很低，确实存在更高效的实现方式，这里推荐两种常用方案：

方案一：一次遍历维护前三大值（O(n) 时间复杂度） #

这是效率最优的方法，只需要遍历列表一次，用几个变量维护当前前三大的值及其对应的索引，不需要额外排序操作，空间复杂度为O(1)。

实现代码（Python）： #

def get_top_three_indices(lst):
    max1 = max2 = max3 = float('-inf')
    idx1 = idx2 = idx3 = -1
    
    for idx, num in enumerate(lst):
        if num > max1:
            max3, idx3 = max2, idx2
            max2, idx2 = max1, idx1
            max1, idx1 = num, idx
        elif num > max2:
            max3, idx3 = max2, idx2
            max2, idx2 = num, idx
        elif num > max3:
            max3, idx3 = num, idx
    return [idx1, idx2, idx3]

test_list = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
print(get_top_three_indices(test_list))  # 输出 [8, 5, 7]

说明： #

遍历过程中，每个元素依次和当前记录的前三大值比较，根据大小关系更新对应的最大值和索引。如果遇到和现有最大值相等的元素，会保留先出现的那个的索引（若需保留后出现的，只需把条件改成>=即可）。

方案二：带索引排序法（O(n log n) 时间复杂度） #

如果追求代码简洁性，且数据量不是极大，可以用这种方法：把列表元素和索引配对后按值降序排序，再取前三个的索引。

实现代码（Python）： #

def get_top_three_indices_sort(lst):
    sorted_pairs = sorted(enumerate(lst), key=lambda x: -x[1])
    return [pair[0] for pair in sorted_pairs[:3]]

test_list = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
print(get_top_three_indices_sort(test_list))  # 输出 [8, 5, 7]

说明： #

这种方法代码更短，可读性强，但排序操作的时间复杂度是O(n log n)，当列表元素达到百万级以上时，效率会比一次遍历的方法低。

方案选择 #

• 处理大规模数据：优先选一次遍历的O(n)方案，性能优势明显。
• 数据量小或追求代码简洁：选带索引排序的方案，实现更快。

内容的提问来源于stack exchange，提问作者Kadaj13