查找两个缺失的数字|集合2（基于异或的解决方案）-yiteyi-C++库

给定一个由n个唯一整数组成的数组，其中数组中的每个元素都在[1，n]范围内。该数组具有所有不同的元素，数组的大小为（n-2）。因此，该数组中缺少两个范围内的数字。找到丢失的两个数字。 例如：

null

Input  : arr[] = {1, 3, 5, 6}, n = 6
Output : 2 4

Input : arr[] = {1, 2, 4}, n = 5
Output : 3 5

Input : arr[] = {1, 2}, n = 4
Output : 3 4

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

找到两个缺失的数字|集1（一个有趣的线性时间解决方案）在上面的文章中，我们讨论了两种解决这个问题的方法。方法1需要额外的O（n）空间，而方法2可能会导致溢出。本文讨论了一种新的解决方案。这里讨论的解决方案是O（n）时间，O（1）额外的空间，并且不会导致溢出。以下是步骤。

求从1到n的所有数组元素和自然数的异或。让数组为arr[]={1,3,5,6}
```
   XOR = (1 ^ 3  ^ 5 ^ 6) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6)
```
根据XOR的性质，相同的元素将被抵消，剩下2个XOR 4=6（110）。但我们不知道确切的数字，让它们是X和Y。
只有当X和Y中的对应位不同时，才在异或中设置位。这是理解的关键一步。
我们在XOR中取一个固定位。让我们考虑XOR中最右边的设置位，StIdBITYNO＝010。
现在，如果我们对arr[]和1到n中最右边的位进行异或运算，我们将得到一个重复的数字，比如x。
```
Ex: Elements in arr[] with bit set: {3, 6}
Elements from 1 to n with bit set {2, 3, 6}
Result of XOR'ing all these is x = 2.
```
类似地，如果我们对arr[]和1到n中未设置最右边位的所有元素进行异或，我们将得到另一个元素，比如y。
```
Ex: Elements in arr[] with bit not set: {1, 5}
Elements from 1 to n with bit not set {1, 4, 5}
Result of XOR'ing all these is y = 4 
```

以下是上述步骤的实施情况。

C++

                         // C++ Program to find 2 Missing Numbers using O(1)                       
                         // extra space and no overflow.                       
                         #include<bits/stdc++.h>                       
                                   
                         // Function to find two missing numbers in range                       
                         // [1, n]. This function assumes that size of array                       
                         // is n-2 and all array elements are distinct                       
                         void                                     findTwoMissingNumbers(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 /* Get the XOR of all elements in arr[] and                       
                                                 {1, 2 .. n} */                       
                                                 int                                     XOR = arr[0];                       
                                                 for                                     (                                     int                                     i = 1; i < n-2; i++)                       
                                                 XOR ^= arr[i];                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 XOR ^= i;                       
                                   
                                                 // Now XOR has XOR of two missing elements. Any set                       
                                                 // bit in it must be set in one missing and unset in                       
                                                 // other missing number                       
                                   
                                                 // Get a set bit of XOR (We get the rightmost set bit)                       
                                                 int                                     set_bit_no = XOR & ~(XOR-1);                       
                                   
                                                 // Now divide elements in two sets by comparing rightmost                       
                                                 // set bit of XOR with bit at same position in each element.                       
                                                 int                                     x = 0, y = 0;                                     // Initialize missing numbers                       
                                                 for                                     (                                     int                                     i = 0; i < n-2; i++)                       
                                                 {                       
                                                 if                                     (arr[i] & set_bit_no)                       
                                                 x = x ^ arr[i];                                     /*XOR of first set in arr[] */                       
                                                 else                       
                                                 y = y ^ arr[i];                                     /*XOR of second set in arr[] */                       
                                                 }                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 if                                     (i & set_bit_no)                       
                                                 x = x ^ i;                                     /* XOR of first set in arr[] and                       
                                                 {1, 2, ...n }*/                       
                                                 else                       
                                                 y = y ^ i;                                     /* XOR of second set in arr[] and                       
                                                 {1, 2, ...n } */                       
                                                 }                       
                                   
                                                 printf                                     (                                     "Two Missing Numbers are %d %d"                                     , x, y);                       
                         }                       
                                   
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 3, 5, 6};                       
                                   
                                                 // Range of numbers is 2 plus size of array                       
                                                 int                                     n = 2 +                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
                                   
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find 2 Missing Numbers                       
                         import                                     java.util.*;                       
                                   
                         class                                     GFG {                       
                                   
                                                 // Function to find two missing numbers in range                       
                                                 // [1, n]. This function assumes that size of array                       
                                                 // is n-2 and all array elements are distinct                       
                                                 static                                     void                                     findTwoMissingNumbers(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 /* Get the XOR of all elements in arr[] and                       
                                                 {1, 2 .. n} */                       
                                                 int                                     XOR = arr[                                     0                                     ];                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n-                                     2                                     ; i++)                       
                                                 XOR ^= arr[i];                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 XOR ^= i;                       
                                   
                                                 // Now XOR has XOR of two missing elements.                       
                                                 // Any set bit in it must be set in one missing                       
                                                 // and unset in other missing number                       
                                   
                                                 // Get a set bit of XOR (We get the rightmost                       
                                                 // set bit)                       
                                                 int                                     set_bit_no = XOR & ~(XOR-                                     1                                     );                       
                                   
                                                 // Now divide elements in two sets by comparing                       
                                                 // rightmost set bit of XOR with bit at same                       
                                                 // position in each element.                       
                                                 int                                     x =                                     0                                     , y =                                     0                                     ;                                     // Initialize missing numbers                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n-                                     2                                     ; i++)                       
                                                 {                       
                                                 if                                     ((arr[i] & set_bit_no) >                                     0                                     )                       
                                   
                                                 /*XOR of first set in arr[] */                       
                                                 x = x ^ arr[i];                       
                                                 else                       
                                                 /*XOR of second set in arr[] */                       
                                                 y = y ^ arr[i];                       
                                                 }                       
                                   
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 if                                     ((i & set_bit_no)>                                     0                                     )                       
                                   
                                                 /* XOR of first set in arr[] and                       
                                                 {1, 2, ...n }*/                       
                                                 x = x ^ i;                       
                                                 else                       
                                                 /* XOR of second set in arr[] and                       
                                                 {1, 2, ...n } */                       
                                                 y = y ^ i;                       
                                                 }                       
                                   
                                                 System.out.println(                                     "Two Missing Numbers are "                                     );                       
                                                 System.out.println( x +                                     " "                                     + y);                       
                                                 }                       
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     };                       
                                   
                                                 // Range of numbers is 2 plus size of array                       
                                                 int                                     n =                                     2                                     +arr.length;                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
                                   
                                                 }                       
                                                 }                       
                                   
                         // This code is contributed by Arnav Kr. Mandal.                       

Python3

                         # Python Program to find 2 Missing                       
                         # Numbers using O(1)                       
                         # extra space and no overflow.                       
                                   
                         # Function to find two missing                       
                         # numbers in range                       
                         # [1, n]. This function assumes                       
                         # that size of array                       
                         # is n-2 and all array elements                       
                         # are distinct                       
                         def                                     findTwoMissingNumbers(arr, n):                       
                                   
                                                 # Get the XOR of all                       
                                                 # elements in arr[] and                       
                                                 # {1, 2 .. n}                       
                                                 XOR                                     =                                     arr[                                     0                                     ]                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n                                     -                                     2                                     ):                       
                                                 XOR ^                                     =                                     arr[i]                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n                                     +                                     1                                     ):                       
                                                 XOR ^                                     =                                     i                       
                                   
                                                 # Now XOR has XOR of two                       
                                                 # missing elements. Any set                       
                                                 # bit in it must be set in                       
                                                 # one missing and unset in                       
                                                 # other missing number                       
                                   
                                                 # Get a set bit of XOR                       
                                                 # (We get the rightmost set bit)                       
                                                 set_bit_no                                     =                                     XOR & ~(XOR                                     -                                     1                                     )                       
                                   
                                                 # Now divide elements in two sets                       
                                                 # by comparing rightmost                       
                                                 # set bit of XOR with bit at same                       
                                                 # position in each element.                       
                                                 x                                     =                                     0                       
                                   
                                                 # Initialize missing numbers                       
                                                 y                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,n                                     -                                     2                                     ):                       
                                                 if                                     arr[i] & set_bit_no:                       
                                   
                                                 # XOR of first set in arr[]                       
                                                 x                                     =                                     x ^ arr[i]                       
                                                 else                                     :                       
                                   
                                                 # XOR of second set in arr[]                       
                                                 y                                     =                                     y ^ arr[i]                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n                                     +                                     1                                     ):                       
                                                 if                                     i & set_bit_no:                       
                                   
                                                 # XOR of first set in arr[] and                       
                                                 # {1, 2, ...n }                       
                                                 x                                     =                                     x ^ i                       
                                   
                                                 else                                     :                       
                                   
                                                 # XOR of second set in arr[] and                       
                                                 # {1, 2, ...n }                       
                                                 y                                     =                                     y ^ i                       
                                   
                                   
                                                 print                                     (                                     "Two Missing Numbers are%d %d"                                     %                                     (x,y))                       
                                   
                         # Driver program to test                       
                         # above function                       
                         arr                                     =                                     [                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     ]                       
                                   
                         # Range of numbers is 2                       
                         # plus size of array                       
                         n                                     =                                     2                                     +                                     len                                     (arr)                       
                         findTwoMissingNumbers(arr, n)                       
                                   
                         # This code is contributed                       
                         # by Shreyanshi Arun.                       

C#

                         // Program to find 2 Missing Numbers                       
                         using                                     System;                       
                                   
                         class                                     GFG {                       
                                   
                                                 // Function to find two missing                       
                                                 // numbers in range [1, n].This                       
                                                 // function assumes that size of                       
                                                 // array is n-2 and all array                       
                                                 // elements are distinct                       
                                                 static                                     void                                     findTwoMissingNumbers(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 // Get the XOR of all elements                       
                                                 // in arr[] and {1, 2 .. n}                       
                                                 int                                     XOR = arr[0];                       
                                   
                                                 for                                     (                                     int                                     i = 1; i < n - 2; i++)                       
                                                 XOR ^= arr[i];                       
                                   
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 XOR ^= i;                       
                                   
                                                 // Now XOR has XOR of two missing                       
                                                 // element. Any set bit in it must                       
                                                 // be set in one missing and unset                       
                                                 // in other missing number                       
                                                 // Get a set bit of XOR (We get the                       
                                                 // rightmost set bit)                       
                                                 int                                     set_bit_no = XOR & ~(XOR - 1);                       
                                   
                                                 // Now divide elements in two sets                       
                                                 // by comparing rightmost set bit                       
                                                 // of XOR with bit at same position                       
                                                 // in each element.                       
                                                 int                                     x = 0, y = 0;                       
                                   
                                                 // Initialize missing numbers                       
                                                 for                                     (                                     int                                     i = 0; i < n - 2; i++) {                       
                                   
                                                 if                                     ((arr[i] & set_bit_no) > 0)                       
                                   
                                                 // XOR of first set in arr[]                       
                                                 x = x ^ arr[i];                       
                                   
                                                 else                       
                                                 // XOR of second set in arr[]                       
                                                 y = y ^ arr[i];                       
                                                 }                       
                                   
                                                 for                                     (                                     int                                     i = 1; i <= n; i++) {                       
                                                 if                                     ((i & set_bit_no) > 0)                       
                                                 // XOR of first set in arr[]                       
                                                 // and {1, 2, ...n }                       
                                                 x = x ^ i;                       
                                   
                                                 else                       
                                                 // XOR of second set in arr[]                       
                                                 // and {1, 2, ...n }                       
                                                 y = y ^ i;                       
                                                 }                       
                                   
                                                 Console.WriteLine(                                     "Two Missing Numbers are "                                     );                       
                                                 Console.WriteLine(x +                                     " "                                     + y);                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 1, 3, 5, 6 };                       
                                   
                                                 // Range of numbers is 2 plus                       
                                                 // size of array                       
                                                 int                                     n = 2 + arr.Length;                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Anant Agarwal.                       

PHP

                         <?php                       
                         // PHP Program to find 2 Missing                       
                         // Numbers using O(1) extra                       
                         // space and no overflow.                       
                                   
                         // Function to find two                       
                         // missing numbers in range                       
                         // [1, n]. This function                       
                         // assumes that size of array                       
                         // is n-2 and all array                       
                         // elements are distinct                       
                         function                                     findTwoMissingNumbers(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 // Get the XOR of all                       
                                                 // elements in arr[] and                       
                                                 // {1, 2 .. n}                       
                                                 $XOR                                     =                                     $arr                                     [0];                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     - 2;                                     $i                                     ++)                       
                                                 $XOR                                     ^=                                     $arr                                     [                                     $i                                     ];                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 $XOR                                     ^=                                     $i                                     ;                       
                                   
                                                 // Now XOR has XOR of two                       
                                                 // missing elements. Any set                       
                                                 // bit in it must be set in                       
                                                 // one missing and unset in                       
                                                 // other missing number                       
                                   
                                                 // Get a set bit of XOR                       
                                                 // (We get the rightmost                       
                                                 // set bit)                       
                                                 $set_bit_no                                     =                                     $XOR                                     & ~(                                     $XOR                                     - 1);                       
                                   
                                                 // Now divide elements in two                       
                                                 // sets by comparing rightmost                       
                                                 // set bit of XOR with bit at                       
                                                 // same position in each element.                       
                                   
                                                 $x                                     = 0;                       
                                   
                                                 // Initialize missing numbers                       
                                                 $y                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     - 2;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] &                                     $set_bit_no                                     )                       
                                   
                                                 // XOR of first set in arr[]                       
                                                 $x                                     =                                     $x                                     ^                                     $arr                                     [                                     $i                                     ];                       
                                   
                                                 else                       
                                   
                                                 // XOR of second set in arr[]                       
                                                 $y                                     =                                     $y                                     ^                                     $arr                                     [                                     $i                                     ];                       
                                                 }                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $i                                     &                                     $set_bit_no                                     )                       
                                   
                                                 // XOR of first set in arr[]                       
                                                 // and {1, 2, ...n }                       
                                                 $x                                     =                                     $x                                     ^                                     $i                                     ;                       
                                   
                                                 else                       
                                   
                                                 // XOR of second set in arr[]                       
                                                 // and {1, 2, ...n }                       
                                                 $y                                     =                                     $y                                     ^                                     $i                                     ;                       
                                                 }                       
                                   
                                                 echo                                     "Two Missing Numbers are"                                     ,                                     $x                                     ;                       
                                                 echo                                     ""                                     ,                                     $y                                     ;                       
                         }                       
                                   
                                                 // Driver Code                       
                                                 $arr                                     =                                     array                                     (1, 3, 5, 6);                       
                                   
                                                 // Range of numbers is 2                       
                                                 // plus size of array                       
                                                 $n                                     = 2 +                                     count                                     (                                     $arr                                     );                       
                                   
                                                 findTwoMissingNumbers(                                     $arr                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                                   
                         // Javascript Program to find 2                       
                         // Missing Numbers using O(1)                       
                         // extra space and no overflow.                       
                                   
                         // Function to find two missing numbers in range                       
                         // [1, n]. This function assumes that size of array                       
                         // is n-2 and all array elements are distinct                       
                         function                                     findTwoMissingNumbers(arr, n)                       
                         {                       
                                                 /* Get the XOR of all elements in arr[] and                       
                                                 {1, 2 .. n} */                       
                                                 let XOR = arr[0];                       
                                                 for                                     (let i = 1; i < n-2; i++)                       
                                                 XOR ^= arr[i];                       
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 XOR ^= i;                       
                                   
                                                 // Now XOR has XOR of two missing                       
                                                 // elements. Any set                       
                                                 // bit in it must be set in                       
                                                 // one missing and unset in                       
                                                 // other missing number                       
                                   
                                                 // Get a set bit of XOR                       
                                                 // (We get the rightmost set bit)                       
                                                 let set_bit_no = XOR & ~(XOR-1);                       
                                   
                                                 // Now divide elements in two                       
                                                 // sets by comparing rightmost                       
                                                 // set bit of XOR with bit at same                       
                                                 // position in each element.                       
                                                 let x = 0, y = 0;                                     // Initialize missing numbers                       
                                                 for                                     (let i = 0; i < n-2; i++)                       
                                                 {                       
                                                 if                                     (arr[i] & set_bit_no)                       
                                                 x = x ^ arr[i];                                     /*XOR of first set in arr[] */                       
                                                 else                       
                                                 y = y ^ arr[i];                                     /*XOR of second set in arr[] */                       
                                                 }                       
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 if                                     (i & set_bit_no)                       
                                                 x = x ^ i;                                     /* XOR of first set in arr[] and                       
                                                 {1, 2, ...n }*/                       
                                                 else                       
                                                 y = y ^ i;                                     /* XOR of second set in arr[] and                       
                                                 {1, 2, ...n } */                       
                                                 }                       
                                   
                                                 document.write(`Two Missing Numbers are<br> ${x} ${y}`);                       
                         }                       
                                   
                         // Driver program to test above function                       
                                                 let arr = [1, 3, 5, 6];                       
                                   
                                                 // Range of numbers is 2 plus size of array                       
                                                 n = 2 + arr.length;                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
                                   
                         </script>                       

输出：

Two Missing Numbers are
2 4

时间复杂度：O（n）辅助空间：O（1）没有整数溢出本文由 希瓦姆·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章