在给定的序列中找到最小的未出现的正整数。

Question

我将尝试解决这个问题：

编写一个函数：

class Solution { public int solution(int[] A); }

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

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

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

假设： N 是一个整数，范围在[1..100,000]之间；数组A的每个元素都是一个整数，范围在[-1,000,000..1,000,000]之间。复杂度：预期的最坏时间复杂度为O(N)；预期的最坏空间复杂度为O(N)(不计算输入参数所需的存储空间)。

我编写了以下解决方案，它的性能较差，但我无法找到错误。

public static int solution(int[] A) {

        Set<Integer> set = new TreeSet<>();

        for (int a : A) {
            set.add(a);
        }

        int N = set.size();

        int[] C = new int[N];

        int index = 0;

        for (int a : set) {
            C[index++] = a;
        }

        for (int i = 0; i < N; i++) {

            if (C[i] > 0 && C[i] <= N) {
                C[i] = 0;
            }
        }

        for (int i = 0; i < N; i++) {

            if (C[i] != 0) {
                return (i + 1);
            }
        }

        return (N + 1);
    }

这里提供分数,

我将继续调查，但如果您能看得更清楚，请告诉我。

- Arefe

---

@ruakh Collections.sort()，他的解决方案有效。 - XtremeBaumer

@ruakh 你说得对 :-) ... 但也许这应该放在代码审查上，因为它已经在运行了... - Tim Biegeleisen

@TimBiegeleisen，正确性只有20％，它绝对不适合在代码审查中。只要它根本无法工作，速度就无关紧要。 - Mast

最初的问题是关于Java的，但其他程序员开始提供许多我没有预料到的答案。因此，我现在只删除了Java标签。 - Arefe

在您的问题中：_期望的最坏时间复杂度为O(N)_。但是在a comment中，您要求在codility demo test中获得100%的分数？这里的一些答案对数组进行排序作为其解决方案的一部分，意味着时间复杂度为O(N log(N))而不是O(N)，但仍然报告称他们的解决方案在codility测试中得分100%。您能澄清哪个更重要-希望在测试中得到100％的分数还是算法在渐近意义下的最坏时间复杂度不会超过O(N)？ - Henke

Answer 1

如果期望的运行时间应该是线性的，那么就不能使用 TreeSet，因为它会对输入进行排序，所以需要 O(NlogN) 的时间。因此，应该使用 HashSet，它仅需要 O(N) 的时间来添加 N 个元素。

此外，您不需要4个循环，只需将所有正整数元素添加到一个 HashSet（第一个循环），然后找到不在该集合中的第一个正整数（第二个循环）即可。

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}

- Eran

---

由于输入大小为N，因此不在输入中的第一个正整数最多为N+1（如果输入数组包含1到N之间的所有数字）。因此第二个循环最多运行N+1次迭代。因此时间复杂度为O(N)。 - Eran

在数组为[-1，-3]时返回，请添加以下几行代码：boolean containsPositive = false; for(int a : A) { if(a > 0) { containsPositive = true; break; } } if(!containsPositive) { return 1; }注意：这是完整的代码。请使用这个重写整个方法，并确保您在添加这一行时没有更改原始代码的含义。 - Camilo

这怎么可能是O(n)？？在第二个循环中由于“contains”方法，我觉得它更像是O(nlog(n))。 - yakya

如果您使用HashSet，contains操作的期望时间为O(1)。 - Eran

是的，完全没问题 :) 谢谢。 - yakya

Answer 2

Javascript实现100%结果解决方案：

function solution(A) {
    // only positive values, sorted
    A = A.filter(x => x >= 1).sort((a, b) => a - b)

    let x = 1

    for(let i = 0; i < A.length; i++) {
        // if we find a smaller number no need to continue, cause the array is sorted
        if(x < A[i]) {
            return x
        }
        x = A[i] + 1
    }

    return x
}

- rista404

---

看起来他们改了测试：混沌序列长度为10005（含负数）得到2，预期为101。我认为该网站上的问题写得不太好… - OctaviaLo

function solution(A) { return Array.from(new Set(A.filter((a)=>a=>1))).sort((a,b)=>a-b).reduce((prev,n,i)=>{ if (n===prev) return n+1 else return prev },1) } - Nico

这个可以得到100%的分数。（只是出于好奇运行一下它。） - lesyk

截至2021年8月，该解决方案在Codility网站的所有测试用例集中均通过了100％的测试。 - utkarsh-k

Answer 3

我的Java代码在Codility上取得了100%的结果

import java.util.*;

class Solution {
    public int solution(int[] arr) {

        Arrays.sort(arr);

        int smallest = 1;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == smallest) {
                smallest++;
            }
        }

        return smallest;
    }
}

- Iryna Prokopenko

---

完美的答案。 - Varun Chandran

一个完美的解决方案 - Anirudh Jadhav

"Arrays.sort(arr);" 的时间复杂度为 O(N log(N))，但期望的时间复杂度为 O(N)。 - Aivean

你不需要那些检查。只用排序和那个for循环就可以了。 - Ashish Prajapat

同意 @Aivean 的观点，另一方面，这里的运行时复杂度为 O(N log(N))，但你没有使用额外的空间，因此空间复杂度为 O(1)。 - Alex S

好的，所有这些解决方案都会修改数组...所以我不认为它们是正确的。 - marcolopes

Answer 4

这里是一个高效的Python解决方案：

def solution(A):
    m = max(A)
    if m < 1:
       return 1

    A = set(A)
    B = set(range(1, m + 1))
    D = B - A
    if len(D) == 0:
        return m + 1
    else:
        return min(D)

- Mohammed Alfaki

---

我认为测试用例[-10，-3]会破坏你的解决方案。当你应该返回1时，你会返回-2。 - YagoCaruso

@YagoCaruso if m < 1: 处理它。 - Otieno Rowland

代码中的 A = set(A) 这一行很有意思。如果在创建集合时不重复使用标识符 A，则得分为 88%，而非 100%（也就是说性能测试中有一个失败了）。显然，Python 在创建集合时通过重复使用数组可以更快地工作？对此有何评论？ - Henke

为什么这种方法比执行A = set(A)，然后循环遍历range(1, 100_001)并检查元素是否在A中更有效？set(A)的时间复杂度是O(n)，而循环的时间复杂度是O(m)，其中n是数组的大小（可能为200万），m在1到100K之间。我只得了75%的分数，想知道原因。 - hansaplast

这样做效率非常低。你首先迭代一次集合以获取max(A)，然后再迭代一次以获取set(A)；接着你用range创建一个新的集合，最后又迭代一次A以找到两个集合中的差异。这至少是O(3N)，而这个问题可以在O(N)内解决。 - alelom

在大O符号表示法中，O(3n)=O(n)! 此外，在Python中通常使用内置函数比循环更快且更优化。请提供您的解决方案/代码，并在平台上进行测试，以造福所有人。 - Mohammed Alfaki

Answer 5

• 使用filter从A数组中获取正数且非零的数字
• 对上述筛选出的数组使用sort以升序排序
• 使用map迭代上述结果
  • if语句用于检查当前元素是否小于x, 如果是则返回该元素，否则将当前元素加1并赋值给x

function solution(A) {

    let x = 1
    
    A.filter(x => x >= 1)
     .sort((a, b) => a - b)
     .map((val, i, arr) => {
        if(x < arr[i]) return
        x = arr[i] + 1
    })

    return x
}

console.log(solution([3, 4, -1, 1]));
console.log(solution([1, 2, 0]));

- Oliv

---

虽然这可能是一个答案，但需要写出解释和细节才能更加清晰明了。 - Ramy M. Mousa

为什么你会在一个标记为 [tag:java] 的问题中给出 JavaScript 的答案？ - Chris

“filter” 仅用于确保原始数组不被改变。 - apena

使用 map 函数时，您不需要使用三个参数，只使用 val 参数就可以正常工作。 - lmendivil

.map((val) => x < val ? x : x = val + 1); - lmendivil

Answer 6

不需要存储任何东西。也不需要哈希集（额外的内存），您可以在遍历数组时完成此操作。但是，该数组必须已排序，并且我们知道最小值为1。

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);     
        int min = 1; 
        /*
         for efficiency — no need to calculate or access the 
         array object’s length property per iteration 
        */
        int cap = A.length; 

        
        for (int i = 0; i < cap; i++){
            if(A[i] == min){
                min++;
            }
        /* 
           can add else if A[i] > min, break; 
           as suggested by punit
         */
        }   
        /*
          min = ( min <= 0 ) ? 1:min; 
          which means: if (min <= 0 ){
          min =1} else {min = min} 
          you can also do: 
          if min <1 for better efficiency/less jumps
         */
        return min;    
    }
}

- TimeTrax

---

你的时间复杂度为 O(N*log(N))，因此违反了问题要求的“...期望最坏时间复杂度为 O(N)；...”的要求。 - Anatolii

在if条件语句中，我们不能这样写： if(A.indexOf(A[i] + 1) < 0){ return min; } - Ujjaval

为什么？请解释一下你的想法。indexOf适用于列表，所以你需要将数组转换为列表或者从一开始就使用ArrayList。如果你非常想使用indexOf，那么你需要知道1是最小值，所以你不需要检查是否等于0，而是检查是否小于1或小于2。如果任何数字加1小于0，作为一个解决方案在逻辑上是具有挑战性的。如果你此时返回，那么你没有检查整个数组中的最小值，只是检查了满足条件的部分。 - TimeTrax

你应该添加一个else条件，如果A[i]>min，则跳出循环。由于数组已经排序，所以不必迭代到最后。 - Punit Tiwan

我认为Java编译器会优化for(;;)语句，只需获取一次A.length，因为在循环中A不会改变。 - user3481644

Answer 7

这是我的PHP解决方案，任务得分100％，正确率100％，性能100％。首先，我们迭代并存储所有正数元素，然后检查它们是否存在。

function solution($A) {

    $B = [];
    foreach($A as $a){ 
        if($a > 0) $B[] = $a;   
    }

    $i = 1;
    $last = 0;
    sort($B);

    foreach($B as $b){

        if($last == $b) $i--; // Check for repeated elements
        else if($i != $b) return $i;

        $i++;
        $last = $b;        

    }

    return $i;
}

我认为这是本站最清晰简单的函数之一，其逻辑可应用于所有其他编程语言。

- Josep Vidal

---

我可以确认 https://app.codility.com/demo/take-sample-test 的总分是100%。（即正确性和性能都是100%。） - Henke

我不理解这个例子。 - SalahAdDin

更简单的PHP方法，100%有效率：不在数组中出现的最小整数……并且这个答案是在这个答案之前一年发布的。 - mickmackusa

Answer 8

对于Swift 4

public func solution(_ A : inout [Int]) -> Int {
  let positive = A.filter { $0 > 0 }.sorted()
  var x = 1
  for val in positive {
  // if we find a smaller number no need to continue, cause the array is sorted
    if(x < val) {
      return x
    }
    x = val + 1
  }
  return x
}

- Pouya ghasemi

---

不行，因为存在冗余元素而失败。例如 [4, 1, 2, 2] 就无法工作。 - Karoly Nyisztor

Answer 9

我通过以下Python解决方案获得了100％的成绩：

def solution(A):
   a=frozenset(sorted(A))
   m=max(a)
   if m>0:
       for i in range(1,m):
           if i not in a:
              return i
       else:
          return m+1
   else:
       return 1

- Farzand

Answer 10

Ruby中的我的回答

def smallest_pos_integer(arr)
  sorted_array = arr.select {|x| x >= 1}.sort
  res = 1

  for i in (0..sorted_array.length - 1)
    if res < sorted_array[i]
      return res
    end
    res = sorted_array[i] + 1
  end
  res
end

- Vincent Nguyen