complexity-theory - 比 O(n^2) 算法更好地在包含前 1000 个整数中的 999 个的数组中查找缺失的整数

Question

假设我有一个包含 999 个单元格的数组，其中包含 1-1000 之间的所有数字，但一个数字除外。找到这个号码的最有效方法是什么？我找不到比 O(n squared) 更好的方法。面试官告诉我有更好的方法。我该怎么做？

未排序的数组。

Answer 1

从 1 到 1000 的所有数字的总和是一个已知值。计算数组中数字的总和，然后将两者相减，得出差值。

我们知道 1..n 的总和是 n(n+1)/2。这是数学中相当常见的结果，但是如果您不熟悉它，可以使用各种技术自己推导出它。

因此，您只需要将数组中的数字相加，然后从上面的值中减去该值，您就会知道缺少什么。

在代码中，这将类似于：

int findMissing(int [] inputArray) {
    //In the above scenario, inputArray.size() would be 999
    int range = inputArray.size() + 1;   //so, range is 1000
    int expected = range * (range + 1) * 0.5;  //we expect the sum to be 500,500
    int sum = 0;
    for (int x: inputArray) {
       sum += x;
    }
    //the missing number is the difference between what we expected, and what we found
    return expected - sum; 

这将是一个 O(n) 结果。

Answer 2

像那样：

 int sum = (1000 * 1001) / 2; // sum of the n first integers is: n*(n+1)/2
 for(int i : array) {
    sum -= i;
 }
 return sum;

Answer 3

您可以使用求和， http://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/ ，然后从求和中减去所有单元格的总和。

missingDigit = (Summation - totalFromCells);