Java 在数字数组中查找缺失数字的最快方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2113795/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Quickest way to find missing number in an array of numbers
提问by Thunderhashy
I have an array of numbers from 1 to 100 (both inclusive). The size of the array is 100. The numbers are randomly added to the array, but there is one random empty slot in the array. What is the quickest way to find that slot as well as the number that should be put in the slot? A Java solution is preferable.
我有一个从 1 到 100（包括两个）的数字数组。数组的大小为100。数字随机添加到数组中，但数组中有一个随机空槽。找到该插槽以及应放入该插槽的数字的最快方法是什么？最好使用 Java 解决方案。
采纳答案by Arnkrishn
You can do this in O(n). Iterate through the array and compute the sum of all numbers. Now, sum of natural numbers from 1 to N, can be expressed as Nx(N+1)/2. In your case N=100.
你可以在 O(n) 中做到这一点。遍历数组并计算所有数字的总和。现在，从 1 到 N 的自然数之和可以表示为Nx(N+1)/2。在您的情况下，N=100。
Subtract the sum of the array from Nx(N+1)/2, where N=100.
从 中减去数组的总和Nx(N+1)/2，其中 N=100。
That is the missing number. The empty slot can be detected during the iteration in which the sum is computed.
那就是缺失的数字。可以在计算总和的迭代期间检测空槽。
// 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);
回答by Mick
Another homework question. A sequential search is the best that you can do. As for a Java solution, consider that an exercise for the reader. :P
另一个家庭作业问题。顺序搜索是您能做的最好的选择。至于 Java 解决方案，请将其视为读者练习。:P
回答by jspcal
(sum of 1 to n) - (sum of all values in the array) = missing number
(1 到 n 的总和) - (数组中所有值的总和) = 缺失数
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) idx = i; else sum += arr[i];
}
System.out.println("missing number is: " + (5050 - sum) + " at index " + idx);
回答by giri
Quick sort is the best choice with maximum efficiency....
快速排序是效率最高的最佳选择......
回答by Martin Booth
This is c# but it should be pretty close to what you need:
这是 c#，但它应该非常接近您的需要：
int sumNumbers = 0;
int emptySlotIndex = -1;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == 0)
emptySlotIndex = i;
sumNumbers += arr[i];
}
int missingNumber = 5050 - sumNumbers;
回答by Tushar Gupta
I think the easiest and possibly the most efficient solution would be to loop over all entries and use a bitset to remember which numbers are set, and then test for 0 bit. The entry with the 0 bit is the missing number.
我认为最简单也可能是最有效的解决方案是遍历所有条目并使用位集来记住设置了哪些数字，然后测试 0 位。带有 0 位的条目是缺失的数字。
回答by AshisKumar
//Array is shorted and if writing in C/C++ think of XOR implementations in java as follows.
int num=-1;
for (int i=1; i<=100; i++){
num =2*i;
if(arr[num]==0){
System.out.println("index: "+i+" Array position: "+ num);
break;
}
else if(arr[num-1]==0){
System.out.println("index: "+i+ " Array position: "+ (num-1));
break;
}
}// use Rabbit and tortoise race, move the dangling index faster,
//learnt from Alogithimica, Ameerpet, hyderbad**
回答by MARIU5
The solution that doesn't involve repetitive additions or maybe the n(n+1)/2 formula doesn't get to you at an interview time for instance.
例如，不涉及重复添加或 n(n+1)/2 公式的解决方案在面试时不会出现。
You have to use an array of 4 ints (32 bits) or 2 ints (64 bits). Initialize the last int with (-1 & ~(1 << 31)) >> 3. (the bits that are above 100 are set to 1) Or you may set the bits above 100 using a for loop.
您必须使用 4 个整数（32 位）或 2 个整数（64 位）的数组。用 (-1 & ~(1 << 31)) >> 3 初始化最后一个 int。（高于 100 的位设置为 1）或者您可以使用 for 循环将位设置为高于 100。
- Go through the array of numbers and set 1 for the bit position corresponding to the number (e.g. 71 would be set on the 3rd int on the 7th bit from left to right)
- Go through the array of 4 ints (32 bit version) or 2 ints(64 bit version)
- 遍历数字数组并将数字对应的位位置设置为 1（例如 71 将设置在第 7 位从左到右的第 3 个 int 上）
- 遍历 4 个整数（32 位版本）或 2 个整数（64 位版本）的数组
public int MissingNumber(int a[])
{
int bits = sizeof(int) * 8;
int i = 0;
int no = 0;
while(a[i] == -1)//this means a[i]'s bits are all set to 1, the numbers is not inside this 32 numbers section
{
no += bits;
i++;
}
return no + bits - Math.Log(~a[i], 2);//apply NOT (~) operator to a[i] to invert all bits, and get a number with only one bit set (2 at the power of something)
}
Example: (32 bit version) lets say that the missing number is 58. That means that the 26th bit (left to right) of the second integer is set to 0.
示例：（32 位版本）假设缺少的数字是 58。这意味着第二个整数的第 26 位（从左到右）设置为 0。
The first int is -1 (all bits are set) so, we go ahead for the second one and add to "no" the number 32. The second int is different from -1 (a bit is not set) so, by applying the NOT (~) operator to the number we get 64. The possible numbers are 2 at the power x and we may compute x by using log on base 2; in this case we get log2(64) = 6 => 32 + 32 - 6 = 58.
第一个 int 是 -1（所有位都设置了）所以，我们继续第二个 int 并将数字 32 添加到“no”。第二个 int 与 -1 不同（没有设置位）所以，通过应用我们得到 64 的数的 NOT (~) 运算符。可能的数是 2 的 x 次幂，我们可以通过使用以 2 为底的 log 来计算 x；在这种情况下，我们得到 log2(64) = 6 => 32 + 32 - 6 = 58。
Hope this helps.
希望这可以帮助。
回答by Moses
If the array is randomly filled, then at the best you can do a linear search in O(n) complexity. However, we could have improved the complexity to O(log n) by divide and conquer approach similar to quick sort as pointed by giri given that the numbers were in ascending/descending order.
如果数组是随机填充的，那么您最多可以在 O(n) 复杂度中进行线性搜索。然而，考虑到数字按升序/降序排列，我们可以通过类似于 giri 指出的快速排序的分而治之的方法将复杂性提高到 O(log n)。
回答by Nitesh
This Program finds missing numbers
该程序查找丢失的数字
<?php
$arr_num=array("1","2","3","5","6");
$n=count($arr_num);
for($i=1;$i<=$n;$i++)
{
if(!in_array($i,$arr_num))
{
array_push($arr_num,$i);print_r($arr_num);exit;
}
}
?>
