如何将元组列表目标值查找算法优化至O(n)时间复杂度？

O(n)时间复杂度实现方案 #

核心优化点是将次位元素的存储结构从列表替换为哈希集合，利用集合O(1)平均时间复杂度的存在性查询特性，消除原方案中O(n)耗时的存在性判断步骤，整体时间复杂度降到线性水平。

实现步骤 #

• 单次遍历所有元组，将所有元组的第二个位置元素存入集合second_pos，该步骤时间复杂度O(n)
• 再次单次遍历所有元组的第一个位置元素，判断是否不在second_pos中，符合条件的即为目标元素，该步骤时间复杂度O(n)
  整体仅需两次线性遍历，总时间复杂度为O(n)，空间复杂度为O(n)（用于存储次位元素集合）。

代码示例（Python） #

def find_target(tuples_input):
    second_pos = set()
    for item in tuples_input:
        second_pos.add(item[1])
    for item in tuples_input:
        if item[0] not in second_pos:
            # 题目约定结果唯一，匹配到直接返回
            return item[0]
    return None

# 测试用例
input_list = [(5,6), (6,4), (6,3), (0,5), (1,2), (2,0)]
print(find_target(input_list)) # 输出结果：1

补充说明 #

Python的set底层基于哈希表实现，存在性查询的平均时间复杂度为O(1)，仅极端哈希冲突场景下才会退化到O(n)，常规工程场景下可认为是稳定的O(1)查询效率。

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