优于O(n ^ 2)算法,在包含前1000个整数中的999的数组中找到缺失的整数

Question

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

数组未分类.

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)结果.