寻找缺失的整数（Codility 测试）

Question

我在Codility上遇到了一个非常奇怪的问题，这是任务描述：

Write a function:

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

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer that does not occur in A.

For example, given:

    A[0] = 1
    A[1] = 3
    A[2] = 6
    A[3] = 4
    A[4] = 1
    A[5] = 2

the function should return 5.

Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

以下是我的代码：

class Solution {
    public int solution(int[] A) {
        SortedSet set = new TreeSet();
        for (int i = 0; i < A.length; i++)
            if (A[i] > 0)
                set.add(A[i]);
        Iterator it = set.iterator();
        int previous = 0, element = 0;
        try { previous = (int)it.next(); }
        catch (NoSuchElementException e) { return 1; }
        while (it.hasNext()) {
            element = (int)it.next();
            if (element!=(previous+1)) break;
            previous=element;
        }
        if (previous+1 < 1) return 1;
        return previous+1;
    }
}

代码分析：

http://i.stack.imgur.com/IlMxP.png

我试图弄清楚为什么我的代码只在那个测试中提供了错误的输出，有人能帮助我吗？

先谢谢了！

- Michele Loria

---

由于TreeSet的插入时间，您的代码具有最坏的时间复杂度O(N*Log(N))。 - Sergey Kalinichenko

@dasblinkenlight 是正确的。你的解决方案是O(N*Log(N))，而应该是O(N)。 - Kostya

你可以使用 HashSet 来添加数字，同时在添加时获取最小和最大的正数。现在遍历 min + 1 到 max - 1，看看哪个第一个正数不在 HashSet 中，然后返回它。这应该是 O(N) 时间和 O(N) 空间。 - SomeDude

Answer 1

我的解决方案得分为100/100

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

        int smallest = 1;

        Arrays.sort(A);
        for (int i = 0; i < A.length; i++) {

            if (A[i] == smallest) {

                smallest++;
            }
        }

        return smallest;
    }
}

在测试用例“large_2”上的运行时间最差，为0.292秒。

我认为相当不错。

如果需要解释，请联系我以便我能够扩展答案 :)

干杯。

- Slobodan Antonijević

---

只有一件事我会添加，就是添加一个lastItem变量来确保不会重复计算相同的数字。 - undefined

Answer 2

如果输入为A = [2]，你会得到一个错误：got 3 expected 1。在这种情况下，previous被设置为2，while循环不会进入，并且该方法返回previous + 1，即3，但正确答案是1。

- Giulio Meneghin

---

谢谢，我手动将元素“0”添加到SortedList中解决了问题！ :) - Michele Loria

Answer 3

哈希表解决方案

这是一个使用哈希表的100%解决方案。它是用JS编写的，但在其他语言中上下文类似。

function solution(A) {

    let hashTable = {}, min = 0;
    
    // build the hash table
    for (const num of A) hashTable[num] = 1;

    // return the first available integer
    while(1) if (!hashTable[++min]) return min;
}

- Shaya

Answer 4

另一个O(n)复杂度的答案：

 int solution(int A[]) {
    int smallestPostive=0;
    int maxPositive = 0;
    for (int number: A) { //Find maximum positive
        if (number> maxPositive) {
            maxPositive = number;
        }
    }
    if (maxPositive == 0) { // if all numbers are negative, just return 1
        return smallestPostive+1;
    }
    int[] data = new int[maxPositive]; //new array with all elements up to max number as indexes
    for (int element: A) {  // when you encounter a +ve number, mark it in the array
        if (element> 0)
            data[element-1] = 1;
    }
    for (int count=0; count<maxPositive;count++) {
        if (data[count] == 0) {  // find the unmarked smallest element
            smallestPostive = count+1;
            break;
        }
    }
return smallestPostive==0?maxPositive+1:smallestPostive; //if nothing is marked return max positive +1
}

- Saurabh Kumar

Answer 5

我找到了一个使用二分查找的解决方案，得分为100/100。

以下是代码：

import java.util.*;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int i = 1;
        while (i <= A.length) {
            int res = Arrays.binarySearch(A, i); 
            if (res < 0) {
                return i;
            }
            i++;
        }
        return i;
    }
}

- jeprubio

Answer 6

    import java.util.*;
    
    class Solution {
    
        public int solution(int[] A) {
            // write your code in Java SE 8
            Arrays.sort( A );
    
            //Print array to confirm
            int smallestVal = 1;
            int len = A.length;
            int prev=0;
    
            for(int i=0; i<len; i++){
                // Filtering all values less than 1 AND filtering the duplicates
                if( A[i] >= 1 && prev != A[i]){
                    if(smallestVal == A[i]){
                        smallestVal++;
                    }else{
                        return smallestVal;
                    }
                    prev = A[i];
                }
            }
            return smallestVal;
        }
    
        public static void main(String[] args) {
            Solution sol = new Solution();
            sol.testOutput(new int[]{-9, 1, 2},3);
            sol.testOutput(new int[]{-9, 2},1);
            sol.testOutput(new int[]{92,93,0,-100},1);
            sol.testOutput(new int[]{-1000000},1);
            sol.testOutput(new int[]{-5,6,-3,7,3,10,1000,-4000},1);
            sol.testOutput(new int[]{999999,-1000000,999998,-999999,-999998,1000000},1);
            sol.testOutput(new int[]{4,6,1,0,-9,10,0,-4},2);
            sol.testOutput(new int[]{-1},1);
            sol.testOutput(new int[]{1},2);
            sol.testOutput(new int[]{1000},1);
            sol.testOutput(new int[]{9,10, 12,1000000},1);
            sol.testOutput(new int[]{1, 3, 6, 4, 1, 2},5);
            sol.testOutput(new int[]{0, 2, 3},1);
            sol.testOutput(new int[]{-1,-3,-10,-100},1);
            sol.testOutput(new int[]{100, 98, 93,78,84, 34,0,1,2,102,130,123,150,200,199,185,149},3);
            sol.testOutput(new int[]{10,9,8,8,7,6,5,4,3,2,1,0,20,19,18,17,16,15,14,13,12},11);
        }
    
        private void testOutput(int[] in, int exp){
            Solution sol = new Solution();
            if(sol.solution(in) == exp){
                System.out.println("PASS");
            }else{
                System.out.println("Expected/Got:"+exp+" / " + sol.solution(in));
            }
        }
    }

- Ariya Bala Sadaiappan

---

太棒了，谢谢！非常感谢你提供的代码。 - Bhala T R

Answer 7

由于我们知道绝对最小值只能是1，所以我们可以从那里开始。

   import java.util.Arrays;
    class Solution {
        public int solution(int[] A) {
            Arrays.sort(A);     
            int min = 1; 

            for (int i = 0; i < A.length; i++){
                if(A[i]== min){
                    min++;
                }
            }   
            //min = ( min <= 0 ) ? 1:min;
            return min;    
        }
    }

- TimeTrax

---

你不需要这个：min = ( min < 1 ) ? 1:min;。因为你已经设置了 int min = 1;。并且你只会在代码中递增 min，它永远不会是负数。 - Slobodan Antonijević

Answer 8

这是我的Python代码，使用100% O(N)的复杂度解决了问题。

def solution(A):
    smallest = 1
    B = {a for a in A}

    while(smallest in B):
        smallest += 1

    return smallest

- Gianpaolo Gulletta

Answer 9

基于 @slobodan 的回答，这里有另一种更优化的解决方案：

class Solution {

    public int solution(int[] A) {

        int smallest = 1;

        Arrays.sort(A);

        for (int i = 0; i < A.length; i++) {

            if (A[i] == smallest) {
                smallest++;
            }
            if (A[i] > smallest) {
                return smallest;
            }
        }

        return smallest;
    }
}

- Jöcker

Answer 10

我曾经通过将所有数据添加到哈希集中，并使用数组索引来检查哈希集来做过类似的事情。还有一些边缘情况需要考虑。您也可以通过添加到哈希映射表中，并使用数组索引按顺序查找日期来实现相同的结果，因为键集是一个集合。

https://app.codility.com/demo/results/trainingVHZNXJ-68S/

 public int solution(int[] A) {
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < A.length; i++) {
      set.add(A[i]);
    }

    int max = 0, missing = -1;
    for (int i = 1; i <= A.length; i++) {
      max = i;
      if (!set.contains(i)) {
        missing = i;
        break;
      }
    }
    return missing == -1 ? max + 1 : missing;
  }

- Luke Samad