complexity-theory - 在包含前 1000 个整数中的 999 个的数组中查找丢失的整数优于 O(n^2) 算法

Question

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

未排序的数组。

Answer 1

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

We know that the sum of from 1..n is 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) 的结果。