基于比较查找元组列表目标索引及低效代码优化需求

首先你的原代码逻辑和需求不匹配：你要找的是元组的第二个元素小于所有其他元组的第一个元素的索引，但原代码只要存在某一个元组的第一个元素大于等于当前元组的第二个元素，就把索引加入集合，这会错误包含很多不符合要求的项（比如示例中索引6的元组，第二个元素11.6虽然大于索引3元组的第一个元素0.9856，但因为存在索引0元组的第一个元素12.4967≥11.6，会被原代码错误加入集合）。

优化思路 #

要高效解决这个问题，核心是预处理所有元组第一个元素的极值信息，避免O(n²)的双层循环：

1. 提取所有元组的第一个元素组成列表；
2. 计算该列表的最小值、次小值，以及最小值的出现次数；
3. 针对每个元组判断是否符合条件：
   • 若最小值出现多次：只要当前元组的第二个元素≤最小值，就符合要求（因为其他元组中必然存在第一个元素等于最小值的项）；
   • 若最小值仅出现一次：
     • 若当前元组不是最小值对应的元组：需要它的第二个元素≤最小值；
     • 若当前元组是最小值对应的元组：需要它的第二个元素≤次小值（因为其他元组的第一个元素最小值是次小值）。

优化后代码 #

b = [(12.4967,12.6328), (2.7100, 13.5921), (2.3388, 12.0418), (0.9856, 13.8039), (5.2956, 12.2421), (3.9076, 13.0671), (6.3806, 11.6), (3.7320, 12.1615), (10.6809, 14.3437)]

# 提取所有元组的第一个元素
firsts = [t[0] for t in b]

# 计算最小值、次小值和最小值出现次数
min1 = float('inf')
min2 = float('inf')
count_min = 0

for num in firsts:
    if num < min1:
        min2 = min1
        min1 = num
        count_min = 1
    elif num == min1:
        count_min += 1
    elif num < min2:
        min2 = num

result = set()
min_idx = firsts.index(min1) if count_min == 1 else -1

for idx, (_, second) in enumerate(b):
    if count_min > 1:
        if second <= min1:
            result.add(idx)
    else:
        if idx != min_idx:
            if second <= min1:
                result.add(idx)
        else:
            if second <= min2:
                result.add(idx)

print(result)

复杂度对比 #

原代码时间复杂度为O(n²)，优化后的代码时间复杂度为O(n)，数据量越大，效率提升越显著。

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