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

arrays algorithm java

2022-08-31 14:37:22

我有一个从1到100（包括1）的数字数组。数组的大小为 100。这些数字被随机添加到数组中，但数组中有一个随机的空插槽。找到该插槽以及应放入插槽中的数字的最快方法是什么？Java解决方案是可取的。

答案 1

您可以在 O（n）中执行此操作。循环访问数组并计算所有数字的总和。现在，从 1 到 N 的自然数之和可以表示为。在你的例子中，N = 100。Nx(N+1)/2

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

这是缺失的数字。在计算总和的迭代期间，可以检测到空槽。

// 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);

答案 2

我们可以使用比求和更安全的XOR运算，因为在编程语言中，如果给定的输入很大，它可能会溢出并可能给出错误的答案。

在转到解决方案之前，请先了解 .因此，如果我们XOR两个相同的数字，则值为0。A xor A = 0

现在，使用数组中存在的元素进行 XOR 运算 [1..n] 会取消相同的数字。因此，在最后，我们将得到丢失的数字。

// Assuming that the array contains 99 distinct integers between 1..99
// and empty slot value is zero
int XOR = 0;
for(int i=0; i<100; i++) {
    if (ARRAY[i] != 0) // remove this condition keeping the body if no zero slot
        XOR ^= ARRAY[i];
    XOR ^= (i + 1);
}
return XOR;
//return XOR ^ ARRAY.length + 1; if your array doesn't have empty zero slot.