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

Question

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

Answer 1

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

在寻求解决方案之前，请知道A xor A = 0。因此，如果我们对两个相同的数字进行XOR运算，则该值为0。

现在，对数组中存在的元素进行XORing [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.