java - 在数字数组中查找缺失数字的最快方法

Question

这个问题的答案是 community effort 。编辑现有答案以改进这篇文章。它目前不接受新的答案或交互。

我有一个从 1 到 100(包括两者)的数字数组。数组的大小为 100。数字是随机添加到数组中的，但数组中有一个随机的空槽。找到该插槽以及应该放入插槽的数字的最快方法是什么？最好使用 Java 解决方案。

Answer 1

你可以在 O(n) 中做到这一点。遍历数组并计算所有数字的总和。现在，从 1 到 N 的自然数之和可以表示为 Nx(N+1)/2。在您的情况下，N=100。

从 Nx(N+1)/2 中减去数组的总和，其中 N=100。

那是缺少的数字。在计算总和的迭代过程中可以检测到空槽。

// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)
{
    if (arr[i] == 0)
    {
         idx = i; 
    }
    else 
    {
         sum += arr[i];
    }
}

// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is: " + (total - sum) + " at index " + idx);