Python / 最小正整数

Question

我接受了以下 codility 演示任务编写一个函数：

解决方案(A)

给定一个由 N 个整数组成的数组 A，返回 A 中不出现的最小正整数（大于 0）。

例如，给定 A = [1, 3, 6, 4, 1, 2]，函数应该返回 5。

给定 A = [1, 2, 3]，函数应该返回 4。

给定 A = [?1, ?3]，函数应该返回 1。

为以下假设编写一个有效的算法：

N 是 [1..100,000] 范围内的整数；数组 A 的每个元素都是 [?1,000,000..1,000,000] 范围内的整数。

我的解决方案

def solution(A):
    # write your code in Python 3.6
    l = len(A)
    B = []
    result = 0
    n = 0
    for i in range(l):
        if A[i] >=1:
            B.append(A[i]) 
    if B ==[]:
        return(1)
    else:    
       B.sort() 
       B = list(dict.fromkeys(B))
       n = len(B)
       for j in range(n-1):
           if B[j+1]>B[j]+1:
                result = (B[j]+1)
       if result != 0:
            return(result)
       else:
            return(B[n-1]+1)

尽管我尝试的所有输入都得到了正确的输出，但我的分数仅为 22%。有人可以请强调我哪里出错了。

Answer 1

时间复杂度为 O(N) 空间复杂度为 O(N) 的 Python 解决方案：

def solution(A):
    arr = [0] * 1000001
    for a in A:
        if a>0:
            arr[a] = 1
    for i in range(1, 1000000+1):
        if arr[i] == 0:
            return i

我的主要想法是：

1. 为所有积极的可能性创建一个零初始化的“桶”。
2. 迭代 A。当你遇到一个正数时，将它的桶标记为已访问 (1)。
3. 迭代“桶”并返回第一个零“桶”。