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. 迭代“桶”并返回第一个零“桶”。