Python中遍历大数组查找首个缺失整数的最高效方法

原代码存在的性能问题 #

• 列表的in操作是线性遍历，每次查询时间复杂度为O(n)，原代码整体时间复杂度达到O(n²)，当输入长度为1e5的列表时，运算量会达到1e10量级，远超正常可接受范围
• 遍历范围冗余：首个缺失的正整数最大只会等于列表长度+1，不需要遍历到100001。比如长度为4的列表如果正好包含1、2、3、4，缺失的就是5，否则缺失值一定在1~4区间内

优化方案 #

方案1：集合预存储（易理解易实现） #

将输入列表转为集合，集合的in查询时间复杂度为O(1)，整体时间复杂度降到O(n)，空间复杂度为O(n)，对于1e5长度的输入完全满足性能要求：

def find_missing(nums):
    n = len(nums)
    num_set = set(nums)
    for i in range(1, n + 1):
        if i not in num_set:
            return i
    return n + 1

方案2：原地哈希（空间最优） #

利用输入列表本身的空间做标记，把数值为x的元素放到列表索引为x-1的位置，全部整理完成后遍历列表，第一个索引i对应的数值不等于i+1的，i+1就是缺失值。该方案时间复杂度为O(n)，空间复杂度为O(1)，不需要额外存储开销：

def find_missing(nums):
    n = len(nums)
    for i in range(n):
        # 把符合范围的元素交换到正确位置
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
    # 查找首个位置不匹配的正整数
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

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