找到给定序列中不存在的最小正整数

Question

我试图解决下面提供的Codility中的问题,

写一个函数:

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)(不计算输入参数所需的存储空间).

我写下面的解决方案,性能很低,但是,我看不到这个bug.

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);
    }

分数在这里提供,

我会继续调查自己,但如果你能看得更清楚,请通知我.

谢谢.

Answer 1

如果预期的运行时间应该是线性的,则不能使用a TreeSet,它对输入进行排序,因此需要O(NlogN).因此,您应该使用a 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;
    }
}

Answer 2

无需存储任何东西。不需要哈希集。（额外的内存），您可以在数组中移动时执行此操作。但是，必须对数组进行排序。我们知道最小的值是 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;    
    }
}

Answer 3

我通过以下 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

Answer 4

我的 Java 代码，100% 导致 Codility

import java.util.*;

class Solution {
   public int solution(int[] arr) {
     int smallestInt = 1; 

    if(arr.length == 0) return smallestInt;

    Arrays.sort(arr);

    if(arr[0] > 1) return smallestInt;
    if(arr[ arr.length - 1] <= 0 ) return smallestInt; 

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

    return smallestInt;
}

}

Answer 5

这是一个有效的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)

Answer 6

该解决方案是用 C# 编写的，但以 100% 的分数完成测试

public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    var positives = A.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();
    if(positives.Count() == 0) return 1;
    int prev = 0;
    for(int i =0; i < positives.Count(); i++){

        if(positives[i] != prev + 1){
            return prev + 1;
        }
         prev = positives[i];
    }
    return positives.Last() + 1;
}

Answer 7

对于 Swift 4

func solution(_ A : [Int]) -> Int {
     var 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

}

Answer 8

这是我的 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;
}

我认为它是这里最简单的功能之一，该逻辑可以应用于所有其他语言。

Answer 9

这个答案在Python中给出了100%。最坏情况复杂度 O(N)。

这个想法是，我们不关心序列中的负数，因为我们想要找到不在序列 A 中的最小正整数。因此，我们可以将所有负数设置为零并仅保留唯一的正值。然后我们从 1 开始迭代检查该数字是否在序列 A 的正值集合中。

最坏的情况是，序列是差值为 1 的算术级数，导​​致迭代所有元素，从而导致 O(N) 复杂度。

在序列中所有元素均为负数（即最大值为负数）的极端情况下，我们可以立即返回 1 作为最小正数。

def solution(A):
    max_A=max(A)
    B=set([a if a>=0 else 0 for a in A ])
    b=1
    if max_A<=0:
        return(1)
    else:
        while b in B:
            b+=1
        return(b)

Answer 10

JS：

• filter 从数组中获取正的非零数
• 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]));

Answer 11

JavaScript 解决方案：

function solution(A) {
    A = [...new Set(A.sort( (a,b) => a-b))];

    // If the initial integer is greater than 1 or the last integer is less than 1
    if((A[0] > 1) || (A[A.length - 1] < 1)) return 1;

    for (let i in A) {
        let nextNum = A[+i+1];
        if(A[i] === nextNum) continue;
        if((nextNum - A[i]) !== 1) {
            if(A[i] < 0 ) {
                if(A.indexOf(1) !== -1) continue;
                return 1;
            }
            return A[i] + 1;
        }
    }
}

Answer 12

我的JavaScript解决方案，使用reduce()方法

function solution(A) {
  // the smallest positive integer = 1
  if (!A.includes(1)) return 1;

  // greater than 1
  return A.reduce((accumulator, current) => {
    if (current <= 0) return accumulator
    const min = current + 1
    return !A.includes(min) && accumulator > min ? min : accumulator;
  }, 1000000)
}

console.log(solution([1, 2, 3])) // 4
console.log(solution([5, 3, 2, 1, -1])) // 4
console.log(solution([-1, -3])) // 1
console.log(solution([2, 3, 4])) // 1

https://codesandbox.io/s/the-smallest-positive-integer-zu4s2

Answer 13

Swift 中的 100% 解决方案，我在这里找到了它，它比我的算法真的漂亮......不需要按顺序转动数组，而是使用字典[Int: Bool]，只需检查字典中的正项。

public func solution(_ A : inout [Int]) -> Int {
    var counter = [Int: Bool]()
    for i in A {
        counter[i] = true
    }

    var i = 1
    while true {
        if counter[i] == nil {
            return i
        } else {
            i += 1
        }
    }
}

Answer 14

我想一个简单的方法是使用BitSet.

• 只需将所有正数添加到 BitSet 中即可。
• 完成后，返回位 0 之后第一个清除位的索引。

public static int find(int[] arr) {
    BitSet b = new BitSet();
    for (int i : arr) {
        if (i > 0) {
            b.set(i);
        }
    }
    return b.nextClearBit(1);
}

Answer 15

JavaScript ES6 解决方案：

function solution(A) {
  if (!A.includes(1)) return 1;
  return A.filter(a => a > 0)
    .sort((a, b) => a - b)
    .reduce((p, c) => c === p ? c + 1 : p, 1);
}
console.log(solution([1, 3, 6, 4, 1, 2]));
console.log(solution([1, 2, 3]));
console.log(solution([-1, -3]));
console.log(solution([4, 5, 6]));
console.log(solution([1, 2, 4]));

Answer 16

0. 简介

\n

A) 允许的语言

\n

Codility 技能评估演示测试允许\n以 18 种不同语言编写解决方案：C, C++, C#, Go, Java 8, Java 11, JavaScript, Kotlin, Lua, Objective-C, Pascal, PHP, Perl, Python, Ruby, Scala, Swift 4, Visual Basic.

\n

B）对你的问题的一些评论

\n

\n

我在下面编写了性能较低的解决方案

\n

\n

在获得正确的解决方案之前，没有理由担心性能。\n在考虑算法/代码的速度有多快或多慢之前，请始终确保解决方案是正确的！

\n

\n

预期最坏情况时间复杂度为 O(N)

\n

\n

好吧，作为问题的提出者，\n你可以决定答案中应满足什么要求。\n但如果目标是在 Codility（性能）测试中获得 100% 的分数，\n那么就没有必要要求 O (N)。\n这里的答案中有很多解决方案，它们都是 O(N log N)\n而不是O (N)，但仍然通过了所有 4 个性能测试。\n这证明了时间上的 O(N) 要求复杂性\n不必要地苛刻（如果唯一的目标是在Codility\n测试中获得100%的分数）。

\n

C) 关于此处提出的解决方案

\n

此处提供的所有解决方案要么是\n已发布答案的重构版本，要么是受到此类答案的启发。\n此处的所有解决方案在Codility 技能评估\n演示测试中得分为 100%。\n ¹

\n

我一直努力

\n

\n
• 明确引用每个原始答案/解决方案，
\n
• 为每个解决方案提供可运行的jdoodle链接\n，
\n
• 对所有解决方案使用相同的 8 个测试（我自己选择），
\n
• 选择得分为 100% 的解决方案（意味着正确性为 5 分，\n性能/速度为 4 分），
\n
• 可以轻松地将答案直接复制粘贴到Codility\nskills 评估演示测试中，
\n
• 重点关注一些最常用的语言。
\n

\n

1. Java：Codility 正确性测试不正确（！）

\n

我将使用现有答案之一来证明，当给定数组\n为空时，Codility\n正确性测试对于边缘情况是有缺陷的。
\n在空数组中，最小的缺失正整数显然是 1。\n同意吗？

\n

但 Codility 测试套件似乎接受空数组的任何答案。
\n在下面的代码中，我故意返回-99空数组，\n这显然是不正确的。
\n然而，Codility 为我的有缺陷的解决方案提供了 100% 的测试分数。（！）

\n

import java.util.Arrays;\n\n/**\nhttps://app.codility.com/demo/take-sample-test 100%\nhttps://stackoverflow.com/a/57067307\nhttps://jdoodle.com/a/3B0D\nTo run the program in a terminal window:\n  javac Solution.java && java Solution && rm Solution.class\nTerminal command to run the combined formatter/linter:\n  java -jar ../../../checkstyle-8.45.1.jar -c ../../../google_checks.xml *.java\n*/\npublic class Solution {\n  /** Returns the smallest positive integer missing in intArray. */\n  public static int solution(int[] intArray) {\n    if (intArray.length == 0) { // No elements at all.\n      return -99; // So the smallest positive missing integer is 1.\n    }\n    Arrays.sort(intArray);\n    // System.out.println(Arrays.toString(intArray)); // Temporarily uncomment?\n    if (intArray[0] >= 2) { // Smallest positive int is 2 or larger.\n      return 1; // Meaning smallest positive MISSING int is 1.\n    }\n    if (intArray[intArray.length - 1] <= 0) { // Biggest int is 0 or smaller.\n      return 1; // Again, smallest positive missing int is 1.\n    }\n    int smallestPositiveMissing = 1;\n    for (int i = 0; i < intArray.length; i++) {\n      if (intArray[i] == smallestPositiveMissing) {\n        smallestPositiveMissing++;\n      } // ^^ Stop incrementing if intArray[i] > smallestPositiveMissing. ^^\n    }   // Because then the smallest positive missing integer has been found:\n    return smallestPositiveMissing;\n  }\n\n  /** Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically). */\n  public static void main(String[] args) {\n    System.out.println("Hello Codility Demo Test for Java, B");\n    int[] array1 = {-1, -3};\n    System.out.println(solution(array1));\n    int[] array2 = {1, -1};\n    System.out.println(solution(array2));\n    int[] array3 = {2, 1, 2, 5};\n    System.out.println(solution(array3));\n    int[] array4 = {3, 1, -2, 2};\n    System.out.println(solution(array4));\n    int[] array5 = {};\n    System.out.println(solution(array5));\n    int[] array6 = {1, -5, -3};\n    System.out.println(solution(array6));\n    int[] array7 = {1, 2, 4, 5};\n    System.out.println(solution(array7));\n    int[] array8 = {17, 2};\n    System.out.println(solution(array8));\n  }\n}\n

\n

下面是测试结果的屏幕转储。
\n由于解法明显错误，当然不应该得分100%！\n ²

\n

\n

2.JavaScript

\n

下面是一个 JavaScript 解决方案。
\n这个问题以前没有发布过，但受到了\n之前答案之一的启发。

\n

\r\n

\r\n

/**\nhttps://app.codility.com/demo/take-sample-test 100%\n(c) Henke 2022 https://stackoverflow.com/users/9213345\nhttps://jdoodle.com/a/3AZG\nTo run the program in a terminal window:\n  node CodilityDemoJS3.js\nTerminal command to run the combined formatter/linter:\n  standard CodilityDemoJS3.js\nhttps://github.com/standard/standard\n*/\nfunction solution (A) {\n/// Returns the smallest positive integer missing in the array A.\n  let smallestMissing = 1\n  // In the following .reduce(), the only interest is in `smallestMissing`.\n  // I arbitrarily return \'-9\' because I don\'t care about the return value.\n  A.filter(x => x > 0).sort((a, b) => a - b).reduce((accumulator, item) => {\n    if (smallestMissing < item) return -9 // Found before end of the array.\n    smallestMissing = item + 1\n    return -9 // Found at the end of the array.\n  }, 1)\n  return smallestMissing\n}\n// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).\n// Note! The following lines need to be left out when running the\n// Codility Demo Test at https://app.codility.com/demo/take-sample-test :\nconsole.log(\'Hello Codility Demo Test for JavaScript, 3.\')\nconsole.log(solution([-1, -3]))\nconsole.log(solution([1, -1]))\nconsole.log(solution([2, 1, 2, 5]))\nconsole.log(solution([3, 1, -2, 2]))\nconsole.log(solution([]))\nconsole.log(solution([1, -5, -3]))\nconsole.log(solution([1, 2, 4, 5]))\nconsole.log(solution([17, 2]))

\r\n

.as-console-wrapper { max-height: 100% !important; top: 0; }

\r\n

\r\n

\r\n

\n

3.Python

\n

Python 已经开始与 Java 竞争，成为全球最常用的编程语言之一。\n下面的代码是这个答案
的稍微重写的版本。

\n

#!/usr/bin/env python3\n\'\'\'\nhttps://app.codility.com/demo/take-sample-test 100%\nhttps://stackoverflow.com/a/58980724\nhttps://jdoodle.com/a/3B0k\nTo run the program in a terminal window:\n    python codility_demo_python_a.py\nCommand in the terminal window to run the linter:\n    py -m pylint codility_demo_python_a.py\nhttps://pypi.org/project/pylint/\nDito for autopep8 formatting:\n    autopep8 codility_demo_python_a.py --in-place\nhttps://pypi.org/project/autopep8/\n\'\'\'\n\n\ndef solution(int_array):\n    \'\'\'\n    Returns the smallest positive integer missing in int_array.\n    \'\'\'\n    max_elem = max(int_array, default=0)\n    if max_elem < 1:\n        return 1\n    int_array = set(int_array)  # Reusing int_array although now a set\n    # print(int_array)  # <- Temporarily uncomment at line beginning\n    all_ints = set(range(1, max_elem + 1))\n    diff_set = all_ints - int_array\n    if len(diff_set) == 0:\n        return max_elem + 1\n    return min(diff_set)\n\n\n# Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).\n# Note! The following lines need to be commented out when running the\n# Codility Demo Test at https://app.codility.com/demo/take-sample-test :\nprint(\'Hello Codility Demo Test for Python3, a.\')\nprint(solution([-1, -3]))\nprint(solution([1, -1]))\nprint(solution([2, 1, 2, 5]))\nprint(solution([3, 1, -2, 2]))\nprint(solution([]))\nprint(solution([1, -5, -3]))\nprint(solution([1, 2, 4, 5]))\nprint(solution([17, 2]))\n

\n

4.C#

\n

这是 C# 的解决方案，受到之前答案的启发。

\n

using System;\nusing System.Linq;\n/// https://app.codility.com/demo/take-sample-test 100%\n/// (c) 2021 Henke, /sf/users/644934181/\n/// https://jdoodle.com/a/3B0Z\n/// To initialize the program in a terminal window, only ONCE:\n///   dotnet new console -o codilityDemoC#-2 && cd codilityDemoC#-2\n/// To run the program in a terminal window:\n///   dotnet run && rm -rf obj && rm -rf bin\n/// Terminal command to run \'dotnet-format\':\n///   dotnet-format --include DemoC#_2.cs && rm -rf obj && rm -rf bin\npublic class Solution {\n  /// Returns the smallest positive integer missing in intArray.\n  public int solution(int[] intArray) {\n    var sortedSet =\n      intArray.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();\n    // Console.WriteLine("[" + string.Join(",", sortedSet) + "]"); // Uncomment?\n    if (sortedSet.Length == 0) return 1; // The set is empty.\n    int smallestMissing = 1;\n    for (int i = 0; i < sortedSet.Length; i++) {\n      if (smallestMissing < sortedSet[i]) break; // The answer has been found.\n      smallestMissing = sortedSet[i] + 1;\n    } // Coming here means all of `sortedSet` had to be traversed.\n    return smallestMissing;\n  }\n\n  /// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).\n  /// NOTE! The code below must be removed before running the Codility test.\n  static void Main(string[] args) {\n    Console.WriteLine("Hello Codility Demo Test for C#, 2.");\n    int[] array1 = { -1, -3 };\n    Console.WriteLine((new Solution()).solution(array1));\n    int[] array2 = { 1, -1 };\n    Console.WriteLine((new Solution()).solution(array2));\n    int[] array3 = { 2, 1, 2, 5 };\n    Console.WriteLine((new Solution()).solution(array3));\n    int[] array4 = { 3, 1, -2, 2 };\n    Console.WriteLine((new Solution()).solution(array4));\n    int[] array5 = { };\n    Console.WriteLine((new Solution()).solution(array5));\n    int[] array6 = { 1, -5, -3 };\n    Console.WriteLine((new Solution()).solution(array6));\n    int[] array7 = { 1, 2, 4, 5 };\n    Console.WriteLine((new Solution()).solution(array7));\n    int[] array8 = { 17, 2 };\n    Console.WriteLine((new Solution()).solution(array8));\n  }\n}\n

\n

5.斯威夫特

\n

这是 Swift 的解决方案，取自此答案。

\n

using System;\nusing System.Linq;\n/// https://app.codility.com/demo/take-sample-test 100%\n/// (c) 2021 Henke, https://stackoverflow.com/users/9213345\n/// https://jdoodle.com/a/3B0Z\n/// To initialize the program in a terminal window, only ONCE:\n///   dotnet new console -o codilityDemoC#-2 && cd codilityDemoC#-2\n/// To run the program in a terminal window:\n///   dotnet run && rm -rf obj && rm -rf bin\n/// Terminal command to run \'dotnet-format\':\n///   dotnet-format --include DemoC#_2.cs && rm -rf obj && rm -rf bin\npublic class Solution {\n  /// Returns the smallest positive integer missing in intArray.\n  public int solution(int[] intArray) {\n    var sortedSet =\n      intArray.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();\n    // Console.WriteLine("[" + string.Join(",", sortedSet) + "]"); // Uncomment?\n    if (sortedSet.Length == 0) return 1; // The set is empty.\n    int smallestMissing = 1;\n    for (int i = 0; i < sortedSet.Length; i++) {\n      if (smallestMissing < sortedSet[i]) break; // The answer has been found.\n      smallestMissing = sortedSet[i] + 1;\n    } // Coming here means all of `sortedSet` had to be traversed.\n    return smallestMissing;\n  }\n\n  /// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).\n  /// NOTE! The code below must be removed before running the Codility test.\n  static void Main(string[] args) {\n    Console.WriteLine("Hello Codility Demo Test for C#, 2.");\n    int[] array1 = { -1, -3 };\n    Console.WriteLine((new Solution()).solution(array1));\n    int[] array2 = { 1, -1 };\n    Console.WriteLine((new Solution()).solution(array2));\n    int[] array3 = { 2, 1, 2, 5 };\n    Console.WriteLine((new Solution()).solution(array3));\n    int[] array4 = { 3, 1, -2, 2 };\n    Console.WriteLine((new Solution()).solution(array4));\n    int[] array5 = { };\n    Console.WriteLine((new Solution()).solution(array5));\n    int[] array6 = { 1, -5, -3 };\n    Console.WriteLine((new Solution()).solution(array6));\n    int[] array7 = { 1, 2, 4, 5 };\n    Console.WriteLine((new Solution()).solution(array7));\n    int[] array8 = { 17, 2 };\n    Console.WriteLine((new Solution()).solution(array8));\n  }\n}\n

\n

6.PHP

\n

这是 PHP 的解决方案，取自此答案。

\n

/**\nhttps://app.codility.com/demo/take-sample-test 100%\nhttps://stackoverflow.com/a/57063839\nhttps://www.jdoodle.com/a/4ny5\n*/\npublic func solution(_ A : inout [Int]) -> Int {\n/// Returns the smallest positive integer missing in the array A.\n  let positiveSortedInts = A.filter { $0 > 0 }.sorted()\n// print(positiveSortedInts) // <- Temporarily uncomment at line beginning\n  var smallestMissingPositiveInt = 1\n  for elem in positiveSortedInts{\n  // if(elem > smallestMissingPositiveInt) then the answer has been found!\n    if(elem > smallestMissingPositiveInt) { return smallestMissingPositiveInt }\n    smallestMissingPositiveInt = elem + 1\n  }\n  return smallestMissingPositiveInt // This is if the whole array was traversed.\n}\n// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).\n// Note! The following lines need to be left out when running the\n// Codility Demo Test at https://app.codility.com/demo/take-sample-test :\nprint("Hello Codility Demo Test for Swift 4, A.")\nvar array1 = [-1, -3]\nprint(solution(&array1))\nvar array2 = [1, -1]\nprint(solution(&array2))\nvar array3 = [2, 1, 2, 5]\nprint(solution(&array3))\nvar array4 = [3, 1, -2, 2]\nprint(solution(&array4))\nvar array5 = [] as [Int]\nprint(solution(&array5))\nvar array6 = [1, -5, -3]\nprint(solution(&array6))\nvar array7 = [1, 2, 4, 5]\nprint(solution(&array7))\nvar array8 = [17, 2]\nprint(solution(&array8))\n

\n

参考

\n

\n
• Codility 技能评估演示测试
\n
• LeetCode 游乐场
\n
• 正确的Java解决方案
\n
• 正确的 JavaScript 解决方案
\n
• 正确的 Python 3 解决方案
\n
• 正确的 C# 解决方案
\n
• 正确的 Swift 4 解决方案
\n
• 正确的 PHP 解决方案
\n

\n\n \n

¹ \n即使对于第一个解决方案 \xe2\x80\x93 Java 解决方案 \xe2\x80\x93\n 也是如此，尽管事实上该解决方案是错误的！

\n

^{2您可以尝试在\n} https://app.codility.com/demo/take-sample-test自行运行测试。\n您必须注册才能执行此操作。\n只需复制粘贴来自代码段。\n默认值为Java 8，因此您不需要更改\n第一个解决方案的语言。

\n \n

Answer 17

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
}

Answer 18

我在 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

Answer 19

在 Kotlin 中，得分为 %100 检测到的时间复杂度：O(N) 或 O(N * log(N))

fun solution(A: IntArray): Int {
    var min = 1
    val b = A.sortedArray()
    for (i in 0 until b.size) {
        if (b[i] == min) {
            min++
        }
    }
    return min
}

Answer 20

这是一个简单而快速的PHP代码。

• 任务得分： 100%
• 正确率： 100%
• 性能： 100%
• 检测时间复杂度： O(N) 或 O(N * log(N))

function solution($A) {
    
    $x = 1;
    
    sort($A);
    
    foreach($A as $i){
        
        if($i <=0) continue;
        
        if($x < $i) return $x;
        
        else $x = $i+1; 
        
    }
    
    return $x;
}

性能测试

Answer 21

无排序、100% 得分和 O(N) 运行时间的 JavaScript 解决方案。它在查找最大数的同时构建正数的哈希集。

function solution(A) {
    set = new Set()
    let max = 0
    for (let i=0; i<A.length; i++) {
        if (A[i] > 0) {
            set.add(A[i])
            max = Math.max(max, A[i])
        }
    }

    for (let i=1; i<max; i++) {
        if (!set.has(i)) {
            return i
        }
    }
    return max+1
}