find数字数组中缺失数字的最快方法

我有一个数字从1到100（包括两个端点）的数组。 数组的大小为100.数字随机添加到数组中，但数组中有一个随机空槽。 find那个插槽的最快方法是什么，以及插槽中应该放置的数量是多less？ Java解决scheme是可取的。

Answer 1

你可以在O（n）中做到这一点。 遍历数组并计算所有数字的总和。 现在，从1到N的自然数之和可以表示为Nx(N+1)/2 。 在你的情况N = 100。

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

这是缺less的数字。 在计算总和的迭代期间可以检测到空时隙。

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

Answer 2

 long n = 100; int a[] = new int[n]; //XOR of all numbers from 1 to n // n%4 == 0 ---> n // n%4 == 1 ---> 1 // n%4 == 2 ---> n + 1 // n%4 == 3 ---> 0 long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0; for (long i = 1; i <= n; i++) { xor = xor ^ a[i]; } //Missing number System.out.println(xor); 

Answer 3

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

在去解决之前，知道A xor A = 0 。 所以如果我们XOR两个相同的数字的值是0。

现在，与数组中存在的元素XORing [1..n]将取消相同的数字。 所以最后我们会得到缺less的数字。

 // 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) XOR ^= ARRAY[i]; XOR ^= (i + 1); } return XOR; 

Answer 4

这是一个亚马逊面试的问题，最初是在这里回答的： 我们有从1到52的数字放入一个51数组中，找出哪个数字丢失的最好方法是什么？

回答如下：

 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. 

这里也有博客： 软件工作 – 面试问题

Answer 5

这是一个简单的程序来查找整数数组中缺less的数字

 ArrayList<Integer> arr = new ArrayList<Integer>(); int a[] = { 1,3,4,5,6,7,10 }; int j = a[0]; for (int i=0;i<a.length;i++) { if (j==a[i]) { j++; continue; } else { arr.add(j); i--; j++; } } System.out.println("missing numbers are "); for(int r : arr) { System.out.println(" " + r); } 

Answer 6

5050 – （数组中所有值的总和）=丢失的数字

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

Answer 7

这是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; 

Answer 8

那么，使用布隆filter。

 int findmissing(int arr[], int n) { long bloom=0; int i; for(i=0; i<;n; i++)bloom+=1>>arr[i]; for(i=1; i<=n, (bloom<<i & 1); i++); return i; } 

Answer 9

在类似的情况下， 数组已经sorting ，它不包含重复项，只有一个数字缺失， 可以使用二进制search在log（n）时间find这个缺失的数字 。

 public static int getMissingInt(int[] intArray, int left, int right) { if (right == left + 1) return intArray[right] - 1; int pivot = left + (right - left) / 2; if (intArray[pivot] == intArray[left] + (intArray[right] - intArray[left]) / 2 - (right - left) % 2) return getMissingInt(intArray, pivot, right); else return getMissingInt(intArray, left, pivot); } public static void main(String args[]) { int[] array = new int[]{3, 4, 5, 6, 7, 8, 10}; int missingInt = getMissingInt(array, 0, array.length-1); System.out.println(missingInt); //it prints 9 } 

Answer 10

不涉及重复的添加或者n（n + 1）/ 2公式的解决scheme在面试的时候并没有给你。

您必须使用4位（32位）或2位（64位）的数组。 使用（-1＆〜（1 << 31））>> 3来初始化最后一个int。（高于100的位设置为1）或者可以使用for循环将位设置为100以上。

1. 遍历数字数组，并设置1对应于数字的位的位置（例如71将设置在从左到右的第7位的第3个int）
2. 通过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) }
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) } 

例如：（32位版本）可以说缺less的数字是58.这意味着第二个整数的第26位（从左到右）被设置为0。

第一个int是-1（所有的位都被设置），所以我们继续第二个int，并把数字32加上“no”。第二个int不是-1（一个比特没有设置），所以通过应用NOT（〜）运算符到我们得到的数字64.可能的数字是2的幂x，我们可以通过使用log 2来计算x; 在这种情况下，我们得到log2（64）= 6 => 32 + 32 – 6 = 58。

希望这可以帮助。

Answer 11

这不是一个search问题。 雇主想知道你是否掌握了校验和。 如果你正在寻找多个唯一的整数，你可能需要一个二进制或循环或其他什么，但是这个问题规定了“一个随机的空闲时隙”。 在这种情况下，我们可以使用stream总和。 条件：“数字随机添加到数组”是没有意义的，没有更多的细节。 这个问题并不假定数组必须以整数1开始，所以可以容忍偏移量的起始整数。

 int[] test = {2,3,4,5,6,7,8,9,10, 12,13,14 }; /*get the missing integer*/ int max = test[test.length - 1]; int min = test[0]; int sum = Arrays.stream(test).sum(); int actual = (((max*(max+1))/2)-min+1); //Find: //the missing value System.out.println(actual - sum); //the slot System.out.println(actual - sum - min); 

成功时间：0.18内存：320576信号：0

Answer 12

我发现这个美丽的解决scheme：

http://javaconceptoftheday.com/java-puzzle-interview-program-find-missing-number-in-an-array/

 public class MissingNumberInArray { //Method to calculate sum of 'n' numbers static int sumOfNnumbers(int n) { int sum = (n * (n+1))/ 2; return sum; } //Method to calculate sum of all elements of array static int sumOfElements(int[] array) { int sum = 0; for (int i = 0; i < array.length; i++) { sum = sum + array[i]; } return sum; } public static void main(String[] args) { int n = 8; int[] a = {1, 4, 5, 3, 7, 8, 6}; //Step 1 int sumOfNnumbers = sumOfNnumbers(n); //Step 2 int sumOfElements = sumOfElements(a); //Step 3 int missingNumber = sumOfNnumbers - sumOfElements; System.out.println("Missing Number is = "+missingNumber); } } 

Answer 13

========sorting数组最简单的解决scheme===========

 public int getMissingNumber(int[] sortedArray) { int missingNumber = 0; int missingNumberIndex=0; for (int i = 0; i < sortedArray.length; i++) { if (sortedArray[i] == 0) { missingNumber = (sortedArray[i + 1]) - 1; missingNumberIndex=i; System.out.println("missingNumberIndex: "+missingNumberIndex); break; } } return missingNumber; } 

Answer 14

从一系列数字中找出遗漏的数字。 IMP点要记住。

1. 该数组应该sorting..
2. 该函数不适用于多个错误。

3. 序列必须是一个AP。

     public int execute2(int[] array) { int diff = Math.min(array[1]-array[0], array[2]-array[1]); int min = 0, max = arr.length-1; boolean missingNum = true; while(min<max) { int mid = (min + max) >>> 1; int leftDiff = array[mid] - array[min]; if(leftDiff > diff * (mid - min)) { if(mid-min == 1) return (array[mid] + array[min])/2; max = mid; missingNum = false; continue; } int rightDiff = array[max] - array[mid]; if(rightDiff > diff * (max - mid)) { if(max-mid == 1) return (array[max] + array[mid])/2; min = mid; missingNum = false; continue; } if(missingNum) break; } return -1; } 

Answer 15

我认为最简单也可能是最有效的解决scheme是遍历所有条目，并使用bitset来记住设置了哪些数字，然后testing0位。 0位的条目是缺less的数字。

Answer 16

本程序find缺less的数字

 <?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; } } ?> 

Answer 17

你可以做的一件事就是使用快速sorting来sorting数字。 然后使用for循环遍历从1到100的有序数组。在每次迭代中，如果您发现索引增量与数组值不同，则将数组中的数字与for循环增量进行比较find了你的缺失的数字以及缺less的索引。

Answer 18

下面是find给定数组中所有缺失数字的解决scheme：

 public class FindMissingNumbers { /** * The function prints all the missing numbers from "n" consecutive numbers. * The number of missing numbers is not given and all the numbers in the * given array are assumed to be unique. * * A similar approach can be used to find all no-unique/ unique numbers from * the given array * * @param n * total count of numbers in the sequence * @param numbers * is an unsorted array of all the numbers from 1 - n with some * numbers missing. * */ public static void findMissingNumbers(int n, int[] numbers) { if (n < 1) { return; } byte[] bytes = new byte[n / 8]; int countOfMissingNumbers = n - numbers.length; if (countOfMissingNumbers == 0) { return; } for (int currentNumber : numbers) { int byteIndex = (currentNumber - 1) / 8; int bit = (currentNumber - byteIndex * 8) - 1; // Update the "bit" in bytes[byteIndex] int mask = 1 << bit; bytes[byteIndex] |= mask; } for (int index = 0; index < bytes.length - 2; index++) { if (bytes[index] != -128) { for (int i = 0; i < 8; i++) { if ((bytes[index] >> i & 1) == 0) { System.out.println("Missing number: " + ((index * 8) + i + 1)); } } } } // Last byte int loopTill = n % 8 == 0 ? 8 : n % 8; for (int index = 0; index < loopTill; index++) { if ((bytes[bytes.length - 1] >> index & 1) == 0) { System.out.println("Missing number: " + (((bytes.length - 1) * 8) + index + 1)); } } } public static void main(String[] args) { List<Integer> arrayList = new ArrayList<Integer>(); int n = 128; int m = 5; for (int i = 1; i <= n; i++) { arrayList.add(i); } Collections.shuffle(arrayList); for (int i = 1; i <= 5; i++) { System.out.println("Removing:" + arrayList.remove(i)); } int[] array = new int[n - m]; for (int i = 0; i < (n - m); i++) { array[i] = arrayList.get(i); } System.out.println("Array is: " + Arrays.toString(array)); findMissingNumbers(n, array); } } 

Answer 19

假设你的n为8，我们的数字范围是0-8，在这个例子中，我们可以表示所有9个数字的二进制表示如下0000 0001 0010 0011 0100 0101 0110 0111 1000

在上面的序列中没有缺失的数字，在每一列中零和1的数目是匹配的，但是一旦你删除了1的值就可以说3我们在0和1的列数之间得到一个平衡。 如果列中的0的数目是<= 1的数目，那么我们缺less的数字在这个比特位置将具有0，否则如果0的数目>在这个比特位置的1的数目，那么这个比特位置将是1 。我们testing从左到右的位，在每次迭代中，我们丢掉数组的一半来testing下一个位，或者在每次迭代中丢弃奇数组值或偶数组值，这取决于我们缺乏哪个位上。

下面的解决scheme是在C ++中

 int getMissingNumber(vector<int>* input, int bitPos, const int startRange) { vector<int> zeros; vector<int> ones; int missingNumber=0; //base case, assume empty array indicating start value of range is missing if(input->size() == 0) return startRange; //if the bit position being tested is 0 add to the zero's vector //otherwise to the ones vector for(unsigned int i = 0; i<input->size(); i++) { int value = input->at(i); if(getBit(value, bitPos) == 0) zeros.push_back(value); else ones.push_back(value); } //throw away either the odd or even numbers and test //the next bit position, build the missing number //from right to left if(zeros.size() <= ones.size()) { //missing number is even missingNumber = getMissingNumber(&zeros, bitPos+1, startRange); missingNumber = (missingNumber << 1) | 0; } else { //missing number is odd missingNumber = getMissingNumber(&ones, bitPos+1, startRange); missingNumber = (missingNumber << 1) | 1; } return missingNumber; } 

在每次迭代中，我们将input空间减less2，即N，N / 2，N / 4 … = O（log N），空间为O（N）

 //Test cases [1] when missing number is range start [2] when missing number is range end [3] when missing number is odd [4] when missing number is even 

Answer 20

PHP $ n = 100 ;

 $n*($n+1)/2 - array_sum($array) = $missing_number 

和array_search($missing_number)将给出缺less数字的索引

Answer 21

 function solution($A) { // code in PHP5.5 $n=count($A); for($i=1;$i<=$n;$i++) { if(!in_array($i,$A)) { return (int)$i; } } } 

Answer 22

这里程序的时间复杂度是O（logn）和空间复杂度O（logn）

 public class helper1 { public static void main(String[] args) { int a[] = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12}; int k = missing(a, 0, a.length); System.out.println(k); } public static int missing(int[] a, int f, int l) { int mid = (l + f) / 2; //if first index reached last then no element found if (a.length - 1 == f) { System.out.println("missing not find "); return 0; } //if mid with first found if (mid == f) { System.out.println(a[mid] + 1); return a[mid] + 1; } if ((mid + 1) == a[mid]) return missing(a, mid, l); else return missing(a, f, mid); } } 

Answer 23

 public class MissingNumber { public static void main(String[] args) { int array[] = {1,2,3,4,6}; int x1 = getMissingNumber(array,6); System.out.println("The Missing number is: "+x1); } private static int getMissingNumber(int[] array, int i) { int acctualnumber =0; int expectednumber = (i*(i+1)/2); for (int j : array) { acctualnumber = acctualnumber+j; } System.out.println(acctualnumber); System.out.println(expectednumber); return expectednumber-acctualnumber; } } 

Answer 24

最近我在面试中遇到了类似（不完全一样）的问题，而且我从一位朋友那里听到，在面试中被问到了同样的问题。 所以这里是OP问题的一个答案，还有一些可能会被问到的变化。 在Java中给出了答案的例子，因为它指出：

Java解决scheme是可取的。

解决scheme1：

数字从1到100（包括两个数字）的数组…数字随机添加到数组中，但数组中有一个随机空槽

 public static int findMissing1(int [] arr){ int sum = 0; for(int n : arr){ sum += n; } return (100*(100+1)/2) - sum; } 

说明：此解决scheme（与此处公布的许多其他解决scheme一样）基于Triangular number的公式，它给出了从1到n （在这种情况下， n是100）的所有自然数的总和。 现在我们知道应该从1到100的总和 – 我们只需要减去给定数组中现有数字的实际总和。

解决scheme2：

数组从1到n（意思是最大数量是未知的）

 public static int findMissing2(int [] arr){ int sum = 0, max = 0; for(int n : arr){ sum += n; if(n > max) max = n; } return (max*(max+1)/2) - sum; } 

说明：在这个解决scheme中，由于最大数量没有给出 – 我们需要find它。 find最大数量后 – 逻辑是一样的。

解决scheme3：

数组从1到n（最大数是未知数），数组中有两个随机的空槽

 public static int [] findMissing3(int [] arr){ int sum = 0, max = 0, misSum; int [] misNums = {};//empty by default for(int n : arr){ sum += n; if(n > max) max = n; } misSum = (max*(max+1)/2) - sum;//Sum of two missing numbers for(int n = Math.min(misSum, max-1); n > 1; n--){ if(!contains(n, arr))misNums = new int[]{n, misSum-n}; } return misNums; } private static boolean contains(int num, int [] arr){ for(int n : arr){ if(n == num)return true; } return false; } 

说明：在这个解决scheme中，没有给出最大数量（如前所述），但它也可能缺less两个数字而不是一个。 所以我们首先find缺失数字的总和 – 和以前一样。 第二个发现缺失总数和最后（可能）缺失数量之间的较小数字 – 以减less不必要的search。 第三，因为Java的数组（不是集合）没有方法作为indexOf或contains ，我添加了一个小的可重用的方法为该逻辑。 第四，当find第一个缺失的数字时，第二个是从缺失的总和中减去。 如果只有一个数字丢失，那么数组中的第二个数字将为零。

注意

如果你想在其他语言的例子或其他有趣的变化这个问题 ，欢迎您检查我的Github存储库的采访问题和答案 。

Answer 25

使用总和公式，

 class Main { // Function to ind missing number static int getMissingNo (int a[], int n) { int i, total; total = (n+1)*(n+2)/2; for ( i = 0; i< n; i++) total -= a[i]; return total; } /* program to test above function */ public static void main(String args[]) { int a[] = {1,2,4,5,6}; int miss = getMissingNo(a,5); System.out.println(miss); } } 

参考http://www.geeksforgeeks.org/find-the-missing-number/

Answer 26

  //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** 

Answer 27

如果数组是随机填充的，那么最好在O（n）复杂度下进行线性search。 然而，我们可以通过类似快速sorting的分而治之的方法来提高O（log n）的复杂度，正如giri指出的那样，数字是按升序/降序排列的。

Answer 28

现在，我现在对Big O符号太敏感了，但是你不能像Java那样做一些事情吗？

 for (int i = 0; i < numbers.length; i++) { if(numbers[i] != i+1){ System.out.println(i+1); } } 

其中数字是从1-100的数字。 从我读的问题来看，没有说什么时候写出缺失的数字。

或者，如果你可以将i + 1的值抛入另一个数组，并在迭代后打印出来。

当然，它可能不遵守时间和空间的规则。 就像我说的。 我必须强烈地重视大O.

Answer 29

另一个作业问题。 顺序search是你可以做的最好的。 至于Java解决scheme，请考虑阅读者的练习。 ：P

Answer 30

快速sorting是最高效率的最佳select….