java - 在 Java 数组中查找 "Missing"整数

Question

给定一个数组 A[]长度n ，找到一个“缺失”的号码 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)。