缺少整数变化 - 需要O(n)解决方案

Question

问题来自于Codility编程训练,它听起来如下:我们有一个数组(A []​​),其中n(范围从1到100,000)元素,这些是我们的参数.数组的元素是从-2,147,483,648到2,147,483,647的整数,我们需要找到数组中不存在的最小正整数.当然,这可以在O(n*log n)中轻松完成,方法是将它们全部排序并遍历排序的数组,查找缺少的正数(最后一个操作在我的解决方案中具有O(n)最差的时间复杂度).但根据Codility的说法,这个整体问题可以在O(n)中完成,我看不出有任何办法可以做到这一点.有人可以提供一些技巧让我不被卡住吗？

PS这是一个链接,详细描述了我不允许复制的问题 - https://codility.com/c/intro/demo35UEXH-EAT

Answer 1

根据鸽子原理,数字1,2,...,n + 1中的至少一个不在阵列中.让我们创建一个b大小为n + 1 的布尔数组来存储这些数字是否存在.

现在,我们处理输入数组.如果我们找到从1到n + 1的数字,我们在中标记相应的条目b.如果我们看到的数字不符合这些范围,只需丢弃它并继续下一个.两种情况都是每个输入条目O(1),总O(n).

在我们完成输入处理之后,我们可以b在O(n)中找到布尔数组中的第一个非标记条目.

Answer 2

构建所有值的哈希表.对于数字1到n + 1,检查它们是否在哈希表中.其中至少有一个不是.打印出最低的这个数字.

这是O(n)的预期时间(你可以以很高的概率).请参阅@ Gassa的答案,了解如何避免哈希表支持大小为O(n)的查找表.

Answer 3

今天写了这个,得到了100/100.不是最优雅的解决方案,但易于理解 -

public int solution(int[] A) {
    int max = A.length;
    int threshold = 1;
    boolean[] bitmap = new boolean[max + 1];

    //populate bitmap and also find highest positive int in input list.
    for (int i = 0; i < A.length; i++) {
        if (A[i] > 0 && A[i] <= max) {
            bitmap[A[i]] = true;
        }

        if (A[i] > threshold) {
            threshold = A[i];
        }
    }

    //find the first positive number in bitmap that is false.
    for (int i = 1; i < bitmap.length; i++) {
        if (!bitmap[i]) {
            return i;
        }
    }

    //this is to handle the case when input array is not missing any element.
    return (threshold+1);
}

Answer 4

Java中的100%简单解决方案

public static int solution(final int[] A) 
{   
   Arrays.sort(A);
   int min = 1;

   // Starting from 1 (min), compare all elements, if it does not match 
   // that would the missing number.
   for (int i : A) {
     if (i == min) {
       min++;
     }
   }

   return min;
}

Answer 5

public int solutionMissingInteger(int[] A) {
    int solution = 1;
    HashSet<Integer> hashSet = new HashSet<>();

    for(int i=0; i<A.length; ++i){
        if(A[i]<1) continue;
        if(hashSet.add(A[i])){
            //this int was not handled before
            while(hashSet.contains(solution)){
                solution++;
            }
        }
    }

    return solution;
}

Answer 6

简单的 Java 解决方案。在正确性和性能方面得分为 100/100。

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

}