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

Question

我有一个从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);