Python / 最小正整数

Question

我参加了Codility的一个Demo任务，要求编写一个函数：

def solution(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%。请问有人能够指出我错在哪里吗？

- deega

---

https://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/amp/ - user3064538

我的分数只有22％。你能澄清一下你的意思吗？是否存在自动化测试，导致你得到错误的结果？请提供你失败的案例的输入、期望输出和实际输出。 - MisterMiyagi

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. 为所有正数可能性创建一个零初始化的"buckets"。
2. 遍历 A。每当你遇到一个正数时，将它的“bucket”标记为已访问（1）。
3. 遍历“buckets”，并返回第一个零“bucket”。

- Eliran Shem Tov

Answer 2

def solution(A):
    
    s = set(A)
    for x in range(1,100002):
        if x not in s:
            return x
    pass

并获得了100%的成绩

- JohnnyDH

---

确认，干得好！ - Raoul

Answer 3

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
    # write your code in Python 3.6
    i = 1;
    B = set(A);
    while True:
        if i not in B:
            return i;
        i+=1;

- Growyn

---

得分：100％。通过所有测试用例。 - Growyn

Answer 4

我的JavaScript解决方案。解决方案是对数组进行排序，然后比较数组的相邻元素。复杂度为O(N)。

function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
  A.sort((a, b) => a - b);

  if (A[0] > 1 || A[A.length - 1] < 0 || A.length <= 2) return 1;

  for (let i = 1; i < A.length - 1; ++i) {
    if (A[i] > 0 && (A[i + 1] - A[i]) > 1) {
        return A[i] + 1;
    }
  }

  return A[A.length - 1] + 1;
}

- Antajo Paulson

Answer 5

我尝试了以下方法，并获得了100%的分数。

def solution(A):

    A_set = set(A)
    for x in range(10**5 + 1, 1):
        if x not in A_set:
            return x
    else:
        return 10**5 + 1

- Kraviz

Answer 6

这是我的解决方案

def solution(A):
    # write your code in Python 3.8.10
    new = set(A)
    max_ = abs(max(A)) #use the absolute here for negative maximum value
    for num in range(1,max_+2):
        if num not in new:
            return num

- Hardey

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community

Answer 7

我的解决方案（100%通过）：

def solution(nums):

    nums_set = set()
    for el in nums:
        if el > 0 and el not in nums_set:
            nums_set.add(el)

    sorted_set = sorted(nums_set)

    if len(sorted_set) == 0:
        return 1

    if sorted_set[0] != 1:
        return 1

    for i in range(0, len(sorted_set) - 1, 1):
        diff = sorted_set[i + 1] - sorted_set[i]
        if diff >= 2:
            return sorted_set[i] + 1

    return sorted_set[-1] + 1

- Ola Ziemińska

Answer 8

这个解决方案是一个简单的方法！

def solution(A):
...     A.sort()
...     maxval = A[-1]
...     nextmaxval = A[-2]
...     if maxval < 0:
...             while maxval<= 0:
...                     maxval += 1
...             return maxval
...     else:
...             if nextmaxval + 1 in A:
...                     return maxval +1
...             else:
...                     return nextmaxval + 1

- George m

Answer 9

在Codility中，你必须正确预测其他输入，而不仅仅是示例输入，并且获得良好的性能。我是这样做的：

from collections import Counter
def maior_menos_zero(A):
    if A < 0:
        return 1

    else:
        return 1 if A != 1 else 2

def solution(A):
    if len(A) > 1:
        copia = set(A.copy())
        b = max(A)
        c = Counter(A)
        if len(c) == 1:
            return maior_menos_zero(A[0])

        elif 1 not in copia:
            return 1

        else:
            for x in range(1,b+2):
                if x not in copia:
                    return x
    else:
        return maior_menos_zero(A[0])

完全明白。如果是一个长度为1的数组A，则会调用函数maior_menos_zero。此外，如果它的长度>1但其元素相同（计数器），则再次调用函数maior_menos_zero。最后，如果1不在数组中，则1是其中最小的正整数；否则，1在其中，我们将进行for X in range(1,max(A)+2)循环，并检查其元素是否在A中。此外，为了节省时间，第一次出现X not in A的位置就是最小的正整数。

- Vinícius OA

Answer 10

我的解决方案使用集合（不依赖于问题的边界）：

def solution(A):
    a_positive = [x for x in A if x > 0]
    set_a_positive = set(a_positive)
    if not set_a_positive:
        return 1
    
    max_a_positive = max(a_positive)
    set_b = set(range(1, max_a_positive + 2))
    return min(set_b ^ set_a_positive)

- Caco