在数字数组中查找丢失数字的最快方法
在数字数组中查找丢失数字的最快方法
提问于 2010-01-22 07:27:17
我有一个从1到100 (包括1和100)的数组。数组的大小是100。这些数字是随机添加到数组中的，但数组中有一个随机的空位。查找该插槽的最快方法是什么，以及应该放入该插槽的编号是什么？Java解决方案更可取。
回答 25
Stack Overflow用户
回答已采纳
发布于 2010-01-22 07:32:24
你可以在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);Stack Overflow用户
发布于 2013-07-06 14:18:01
我们可以使用XOR运算，它比求和更安全，因为在编程语言中，如果给定的输入很大，它可能会溢出，并可能给出错误的答案。
在进入解决方案之前，请了解A xor A = 0。因此，如果我们对两个相同的数字进行异或运算，则值为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. Stack Overflow用户
发布于 2011-12-16 19:34:32
这是亚马逊的一个面试问题，最初的答案是：We have numbers from 1 to 52 that are put into a 51 number array, what's the best way to find out which number is missing?
回答如下：
1) Calculate the sum of all numbers stored in the array of size 51.
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.它的博客也在这里：Software Job - Interview Question
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2113795
复制相关文章
相似问题