寻找给定列表中缺失的最小正整数：Python实现与性能疑问

我在编码挑战中遇到了这个问题，测试了三种解法的性能：基于for循环的遍历、结合remove()的检查方法，以及利用集合(set)的运算方法，代码如下：

import timeit
import numpy as np

def findSmallestIntNotInList_for(number_list):
    for i in range(1, len(number_list)+2):
        if i not in number_list:
            return i
        else:
            number_list.remove(i)

def findSmallestIntNotInList_remove(number_list):
    i = 0
    while True:
        i += 1
        if i not in number_list:
            return i
        else:
            number_list.remove(i)

def findSmallestIntNotInList_set(number_list):
    m = range(1, len(number_list)+2)
    return min(set(m)-set(number_list))

lim = 10**(4)
a = list(range(-lim,lim))
b = list(range(-lim,lim))
b.remove(2)
rng = np.random.default_rng(seed=42)
c = list(range(-lim,lim))
rng.shuffle(c)
d = list(range(-2*lim,0))

lists = [a,b,c,d]
for l in lists:
    # 注：原测试代码未传入列表副本，会修改原列表导致后续测试结果失真，此处修正为传入副本
    t1 = timeit.Timer(lambda: findSmallestIntNotInList_remove(l.copy()))
    t2 = timeit.Timer(lambda: findSmallestIntNotInList_for(l.copy()))
    t3 = timeit.Timer(lambda: findSmallestIntNotInList_set(l))
    print('Execution time rem:', t1.timeit(10000), 'seconds')
    print('Execution time for:', t2.timeit(10000), 'seconds')
    print('Execution time set:', t3.timeit(10000), 'seconds')
    print('------------')

本地测试输出如下：

Execution time rem: 1.9298538960000002 seconds
Execution time for: 0.5420050019999998 seconds
Execution time set: 5.828596567999999 seconds
------------
Execution time rem: 1.1942714429999999 seconds
Execution time for: 1.1997454950000002 seconds
Execution time set: 13.85635568 seconds
------------
Execution time rem: 3.0267606810000025 seconds
Execution time for: 0.7885398489999993 seconds
Execution time set: 6.929878771999999 seconds
------------
Execution time rem: 1.1609878240000029 seconds
Execution time for: 1.0680834049999959 seconds
Execution time set: 16.141565139 seconds
------------

我提交了set方法和remove方法的解法，set方法拿到100分，但remove方法仅得25分，可本地计时显示remove方法性能更好，针对相关疑问的解答如下：

疑问1：是否存在remove方法表现糟糕的场景？ #

当然有，典型场景包括：

• 缺失的最小正整数很大：比如列表是[1,2,3,...,100000]，此时remove方法需要遍历并删除1到100000的所有元素，每一步的i not in number_list是O(n)复杂度，remove()操作也是O(n)，整体时间复杂度飙升到O(n²)，远慢于O(n)复杂度的set方法。
• 列表包含大量重复正整数：remove()每次只能删除第一个匹配项，遇到重复值时需要反复检查、删除，进一步放大时间开销。

疑问2：remove方法是否在缓存访问等非计时类性能指标上表现不佳？ #

是的。列表是连续内存结构，remove()操作会导致删除位置后的所有元素移位，频繁的内存移动会大幅降低缓存命中率；同时每次i not in number_list都要从头遍历列表，属于连续的缓存不友好操作。而set是哈希表结构，查找操作的缓存利用更稳定，不会有大量内存移位的额外开销。

疑问3：为何编码挑战给remove方法的评分更低？ #

编码挑战的测试用例必然包含最坏性能场景，比如上述缺失值极大、或存在大量重复正整数的情况，此时remove方法会超时。另外你的remove方法会修改输入列表，很多在线判题系统会认为这是不良副作用（虽然题目没明确禁止，但可能影响测试用例的复用），不过核心原因还是性能不达标。

你的本地测试用例恰好都是缺失值较小的场景（比如b列表缺失的是2，remove方法很快就能返回），这才导致本地计时看起来remove方法更快，但无法代表所有测试场景。

疑问4：为何普通for循环比while结构更快？ #

Python的for循环是基于预先生成的range对象迭代，底层由C实现，开销极小；而while循环需要在Python层面手动执行i +=1和条件判断，每一步的操作开销都比C实现的range迭代大。当循环次数较多时，这种差异会被放大，导致for循环明显更快。

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