Python求解未出现最小正整数的解法性能测试未通过，求原因

你当前的解法仅通过1个性能测试，核心问题出在时间复杂度太高：

你的代码里，A.index(val)是列表的线性查找操作，每次查找都要遍历整个列表，时间复杂度为O(n)。如果输入的列表是[1,2,3,...,100000]这类连续正整数，循环会执行100001次，每次都要遍历10万元素，总时间复杂度达到O(n²)。面对大规模测试用例时，这种解法会因为超时无法通过性能测试。

优化方案1：用集合实现O(1)查找（简单易理解） #

把列表转成集合后，成员查询的时间复杂度降到O(1)，整体时间复杂度变为O(n)，能轻松应对大规模数据：

def solution(A):
    num_set = set(A)
    val = 1
    while val in num_set:
        val += 1
    return val

优化方案2：原地哈希（空间复杂度O(1)） #

如果要求不使用额外空间，可以利用数组下标标记存在的正整数，全程在原数组上操作：

def solution(A):
    n = len(A)
    # 把所有非正整数和超过n的数替换成n+1（我们只关心1~n范围内的数）
    for i in range(n):
        if A[i] <= 0 or A[i] > n:
            A[i] = n + 1
    # 用负数标记对应下标的正整数存在
    for num in A:
        abs_num = abs(num)
        if abs_num <= n:
            A[abs_num - 1] = -abs(A[abs_num - 1])
    # 第一个正数对应的下标+1就是答案
    for i in range(n):
        if A[i] > 0:
            return i + 1
    # 所有1~n都存在，返回n+1
    return n + 1

内容的提问来源于stack exchange，提问作者Emmanuel John Gerasta