在Java数组中查找"缺少"整数

Question

给定长度为n的数组A [],找到"缺失"数字k,使得:

• k不在A中
• 0 <= K <= N

我已经看到类似的问题,其中A []包含数字1到n,其中一个数字丢失,但在这个问题中,A []可以包含任何数字.我需要O(n)时间的解决方案.例如,

A = {1,2,3} -> 0
A = {0,1,2} -> 3
A = {2,7,4,1,6,0,5,-3} -> 3,8

我已经检查了数组中是否有0或n,如果没有,则返回0或n,但我似乎无法想到任何其他解决方案.考虑到A可以包含任何数字而不一定是数字1到n或类似的事实,这个问题似乎要困难得多.

Answer 1

线性迭代数组并"交叉"您遇到的每个数字.然后再次迭代列出的划掉的数字,看看哪一个丢失了.

 public static int getMissingNumber(int[] A) 
 {  
    int n = A.length;  
    boolean[] numbersUsed = new boolean[n + 1]; //Because the definition says 0 <= k <= n, so k = n is also possible.

    for(int k = 0; k < n; k++) 
    {
        if(A[k] <= n && A[k] >= 0) //No negative numbers!
           numbersUsed[A[k]] = true;
    }

    for(int k = 0; k <= n; k++) 
    {
       if(numbersUsed[k] == false) 
          return k;
    } 
    return -1; //nothing found
 }   

由于两个for循环,复杂性是2*n ,给出了整体复杂性O(n).