我使用Java 8和Java 8之前的版本编写代码。 它使用一个公式:(N*(N+1))/2作为所有数字的和。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

   /**
 * 
 * 
 * @author pradeep
 * 
 *         Answer : SumOfAllNumbers-SumOfPresentNumbers=Missing Number;
 * 
 *         To GET SumOfAllNumbers : Get the highest number (N) by checking the
 *         length. and use the formula (N*(N+1))/2
 * 
 *         To GET SumOfPresentNumbers: iterate and add it
 * 
 * 
 */
public class FindMissingNumber {
    /**
     * Before Java 8
     * 
     * @param numbers
     * @return
     */
    public static int missingNumber(List<Integer> numbers) {
        int sumOfPresentNumbers = 0;
        for (Integer integer : numbers) {
            sumOfPresentNumbers = sumOfPresentNumbers + integer;
        }
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    /**
     * Using Java 8 . mapToInt & sum using streams.
     * 
     * @param numbers
     * @return
     */
    public static int missingNumberJava8(List<Integer> numbers) {
        int sumOfPresentNumbers = numbers.stream().mapToInt(i -> i).sum();
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list = Arrays.asList(0, 1, 2, 4);
        System.out.println("Missing number is :  " + missingNumber(list));
        System.out.println("Missing number using Java 8 is : " + missingNumberJava8(list));
    }
}*

我让一个4岁的孩子来解决这个问题。他把数字分类，然后开始数。这有一个O(厨房地板)的空间要求，它的工作就像许多球丢失一样简单。

您可以使用二分搜索来查找缺失(或连续)数字的间隔。运行时间应该是(num间隔)* log(平均间隔长度)* n。如果间隔不多，则很有用。

我相信我有一个O(k)时间和O(log(k)空间算法，前提是你有任意大整数的下限(x)和log2(x)函数:

你有一个k位的长整数(因此是log8(k)空间)，其中你加上x^2，其中x是你在袋子里找到的下一个数字:s=1^2+2^2+…这需要O(N)时间(这对面试官来说不是问题)。最后得到j= (log2(s))这是你要找的最大的数。然后s=s-j，重复上面的步骤:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

现在，对于2756位的整数，通常没有floor和log2函数，而是用于double。所以呢?简单地说，对于每2个字节(或1、3、4)，您可以使用这些函数来获得所需的数字，但这增加了O(N)因素的时间复杂度

一个可能的解决方案:

public class MissingNumber {
    public static void main(String[] args) {
        // 0-20
        int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
        printMissingNumbers(a,20);
    }

    public static void printMissingNumbers(int [] a, int upperLimit){
        int b [] = new int[upperLimit];
        for(int i = 0; i < a.length; i++){
            b[a[i]] = 1;
        }
        for(int k = 0; k < upperLimit; k++){
            if(b[k] == 0)
                System.out.println(k);
        }
    }
}

我还没有检查数学，但我怀疑在计算Σ(n)的同时计算Σ(n^2)将提供足够的信息来得到两个缺失的数字，如果有三个，也要计算Σ(n^3)，等等。