找到重复和缺失|添加3种新方法-yiteyi-C++库

给定一个大小为n的未排序数组。数组元素在1到n的范围内。集合{1，2，…n}中的一个数字缺失，一个数字在数组中出现两次。找到这两个数字。

null

例如：

 Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array, 
2 is missing and 3 occurs twice 

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

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

以下是解决问题的各种方法：

方法1（使用排序） 方法：

对输入数组进行排序。
遍历数组并检查是否丢失和重复。

时间复杂性： O（nLogn）

幸亏 LoneShadow 感谢你提出这种方法。

方法2（使用计数数组） 方法：

创建一个大小为n的临时数组temp[]，所有初始值为0。
遍历输入数组arr[]，并对每个arr[i]执行以下操作
- 如果（temp[arr[i]]=0）temp[arr[i]=1；
- if（temp[arr[i]==1）输出“arr[i]”//重复
遍历temp[]并输出值为0的数组元素（这是缺少的元素）

时间复杂性： O（n）

辅助空间： O（n）

方法3（使用元素作为索引并标记访问的地点） 方法： 遍历数组。遍历时，使用每个元素的绝对值作为索引，并将该索引处的值设为负值，以标记它已访问。如果某个元素已经标记为负数，那么这就是重复元素。若要查找缺失，请再次遍历数组并查找正值。

C++

                         // C++ program to Find the repeating                       
                         // and missing elements                       
                                   
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         void                                     printTwoElements(                                     int                                     arr[],                                     int                                     size)                       
                         {                       
                                                 int                                     i;                       
                                                 cout <<                                     " The repeating element is "                                     ;                       
                                   
                                                 for                                     (i = 0; i < size; i++) {                       
                                                 if                                     (arr[                                     abs                                     (arr[i]) - 1] > 0)                       
                                                 arr[                                     abs                                     (arr[i]) - 1] = -arr[                                     abs                                     (arr[i]) - 1];                       
                                                 else                       
                                                 cout <<                                     abs                                     (arr[i]) <<                                     ""                                     ;                       
                                                 }                       
                                   
                                                 cout <<                                     "and the missing element is "                                     ;                       
                                                 for                                     (i = 0; i < size; i++) {                       
                                                 if                                     (arr[i] > 0)                       
                                                 cout << (i + 1);                       
                                                 }                       
                         }                       
                                   
                         /* Driver code */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 7, 3, 4, 5, 5, 6, 2 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 printTwoElements(arr, n);                       
                         }                       
                                   
                         // This code is contributed by Shivi_Aggarwal                       

C

                         // C program to Find the repeating                       
                         // and missing elements                       
                                   
                         #include <stdio.h>                       
                         #include <stdlib.h>                       
                                   
                         void                                     printTwoElements(                                     int                                     arr[],                                     int                                     size)                       
                         {                       
                                                 int                                     i;                       
                                                 printf                                     (                                     " The repeating element is"                                     );                       
                                   
                                                 for                                     (i = 0; i < size; i++) {                       
                                                 if                                     (arr[                                     abs                                     (arr[i]) - 1] > 0)                       
                                                 arr[                                     abs                                     (arr[i]) - 1] = -arr[                                     abs                                     (arr[i]) - 1];                       
                                                 else                       
                                                 printf                                     (                                     " %d "                                     ,                                     abs                                     (arr[i]));                       
                                                 }                       
                                   
                                                 printf                                     (                                     "and the missing element is "                                     );                       
                                                 for                                     (i = 0; i < size; i++) {                       
                                                 if                                     (arr[i] > 0)                       
                                                 printf                                     (                                     "%d"                                     , i + 1);                       
                                                 }                       
                         }                       
                                   
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 7, 3, 4, 5, 5, 6, 2 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 printTwoElements(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to Find the repeating                       
                         // and missing elements                       
                                   
                         import                                     java.io.*;                       
                                   
                         class                                     GFG {                       
                                   
                                                 static                                     void                                     printTwoElements(                                     int                                     arr[],                                     int                                     size)                       
                                                 {                       
                                                 int                                     i;                       
                                                 System.out.print(                                     "The repeating element is "                                     );                       
                                   
                                                 for                                     (i =                                     0                                     ; i < size; i++) {                       
                                                 int                                     abs_val = Math.abs(arr[i]);                       
                                                 if                                     (arr[abs_val -                                     1                                     ] >                                     0                                     )                       
                                                 arr[abs_val -                                     1                                     ] = -arr[abs_val -                                     1                                     ];                       
                                                 else                       
                                                 System.out.println(abs_val);                       
                                                 }                       
                                   
                                                 System.out.print(                                     "And the missing element is "                                     );                       
                                                 for                                     (i =                                     0                                     ; i < size; i++) {                       
                                                 if                                     (arr[i] >                                     0                                     )                       
                                                 System.out.println(i +                                     1                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     7                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     5                                     ,                                     6                                     ,                                     2                                     };                       
                                                 int                                     n = arr.length;                       
                                                 printTwoElements(arr, n);                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Gitanjali                       

Python3

                         # Python3 code to Find the repeating                       
                         # and the missing elements                       
                                   
                         def                                     printTwoElements( arr, size):                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 if                                     arr[                                     abs                                     (arr[i])                                     -                                     1                                     ] >                                     0                                     :                       
                                                 arr[                                     abs                                     (arr[i])                                     -                                     1                                     ]                                     =                                     -                                     arr[                                     abs                                     (arr[i])                                     -                                     1                                     ]                       
                                                 else                                     :                       
                                                 print                                     (                                     "The repeating element is"                                     ,                                     abs                                     (arr[i]))                       
                                   
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 if                                     arr[i]>                                     0                                     :                       
                                                 print                                     (                                     "and the missing element is"                                     , i                                     +                                     1                                     )                       
                                   
                         # Driver program to test above function */                       
                         arr                                     =                                     [                                     7                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     5                                     ,                                     6                                     ,                                     2                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         printTwoElements(arr, n)                       
                                   
                         # This code is contributed by "Abhishek Sharma 44"                       

C#

                         // C# program to Find the repeating                       
                         // and missing elements                       
                                   
                         using                                     System;                       
                                   
                         class                                     GFG {                       
                                                 static                                     void                                     printTwoElements(                                     int                                     [] arr,                                     int                                     size)                       
                                                 {                       
                                                 int                                     i;                       
                                                 Console.Write(                                     "The repeating element is "                                     );                       
                                   
                                                 for                                     (i = 0; i < size; i++) {                       
                                                 int                                     abs_val = Math.Abs(arr[i]);                       
                                                 if                                     (arr[abs_val - 1] > 0)                       
                                                 arr[abs_val - 1] = -arr[abs_val - 1];                       
                                                 else                       
                                                 Console.WriteLine(abs_val);                       
                                                 }                       
                                   
                                                 Console.Write(                                     "And the missing element is "                                     );                       
                                                 for                                     (i = 0; i < size; i++) {                       
                                                 if                                     (arr[i] > 0)                       
                                                 Console.WriteLine(i + 1);                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 7, 3, 4, 5, 5, 6, 2 };                       
                                                 int                                     n = arr.Length;                       
                                                 printTwoElements(arr, n);                       
                                                 }                       
                         }                       
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to Find the repeating                       
                         // and missing elements                       
                                   
                         function                                     printTwoElements(                                     $arr                                     ,                                     $size                                     )                       
                         {                       
                                                 $i                                     ;                       
                                                 echo                                     "The repeating element is"                                     ,                                     " "                                     ;                       
                                   
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $size                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $arr                                     [                                     abs                                     (                                     $arr                                     [                                     $i                                     ]) - 1] > 0)                       
                                                 $arr                                     [                                     abs                                     (                                     $arr                                     [                                     $i                                     ]) - 1] =                       
                                                 -                                     $arr                                     [                                     abs                                     (                                     $arr                                     [                                     $i                                     ]) - 1];                       
                                                 else                       
                                                 echo                                     (                                     abs                                     (                                     $arr                                     [                                     $i                                     ]));                       
                                                 }                       
                                   
                                                 echo                                     "and the missing element is "                                     ;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $size                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] > 0)                       
                                                 echo                                     (                                     $i                                     + 1);                       
                                                 }                       
                         }                       
                                   
                                                 // Driver Code                       
                                                 $arr                                     =                                     array                                     (7, 3, 4, 5, 5, 6, 2);                       
                                                 $n                                     =                                     count                                     (                                     $arr                                     );                       
                                                 printTwoElements(                                     $arr                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                         // Program to Find the repeating                       
                         // and missing elements                       
                                   
                                                 function                                     printTwoElements(arr,size)                       
                                                 {                       
                                                 var                                     i;                       
                                                 document.write(                                     " The repeating element is "                                     );                       
                                   
                                                 for                                     (i = 0; i < size; i++)                       
                                                 {                       
                                                 var                                     abs_value = Math.abs(arr[i]);                       
                                                 if                                     (arr[abs_value - 1] > 0)                       
                                                 arr[abs_value - 1] = -arr[abs_value - 1];                       
                                                 else                       
                                                 document.write( abs_value);                       
                                                 }                       
                                   
                                                 document.write(                                     "<br> and the missing element is "                                     );                       
                                                 for                                     (i = 0; i < size; i++)                       
                                                 {                       
                                                 if                                     (arr[i] > 0)                       
                                                 document.write (i + 1);                       
                                                 }                       
                         }                       
                                   
                         /* Driver code */                       
                                                 arr =                                     new                                     Array ( 7, 3, 4, 5, 5, 6, 2 );                       
                                                 n = arr.length;                       
                                                 printTwoElements(arr, n);                       
                                   
                                                 // This code is contributed by simranarora5sos                       
                         </script>                       

输出

 The repeating element is 5
and the missing element is 1

时间复杂性： O（n）幸亏 曼尼什·米什拉 感谢你提出这种方法。

方法4（制作两个方程式） 方法：

设x为缺失元素，y为重复元素。
使用公式得到所有数字的总和 S=n（n+1）/2–x+y
用公式得到所有数字的乘积 P=1*2*3*..*n*y/x
以上两个步骤给出了两个方程，我们可以求解方程，得到x和y的值。

时间复杂性： O（n）幸亏消失感谢你提出这个解决方案。

注：当我们计算所有数组元素的乘积和和时，这种方法可能会导致算术溢出。

方法5（使用XOR）

方法：

设x和y为所需的输出元素。
计算所有数组元素的异或。

xor1=arr[0]^arr[1]^arr[2]…。。arr[n-1]

将结果与从1到n的所有数字进行异或运算

xor1=xor1^1^2^^N

结果 xor1 ，除x和y之外，所有元素都将彼此置零。中设置的所有位 xor1 将在x或y中设置。因此，如果我们取 xor1 将数组中的元素分成两组——一组元素具有相同的位集，另一组元素具有相同的未设置位。通过这样做，我们将在一组中得到x，在另一组中得到y。现在，如果我们对第一个集合中的所有元素进行异或运算，我们将得到x，在另一个集合中进行同样的运算，我们将得到y。

以下是上述方法的实施情况：

C++

                         // C++ program to Find the repeating                       
                         // and missing elements                       
                                   
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         /* The output of this function is stored at                       
                         *x and *y */                       
                         void                                     getTwoElements(                                     int                                     arr[],                                     int                                     n,                       
                                                 int                                     * x,                                     int                                     * y)                       
                         {                       
                                                 /* Will hold xor of all elements                       
                                                 and numbers from 1 to n */                       
                                                 int                                     xor1;                       
                                   
                                                 /* Will have only single set bit of xor1 */                       
                                                 int                                     set_bit_no;                       
                                   
                                                 int                                     i;                       
                                                 *x = 0;                       
                                                 *y = 0;                       
                                   
                                                 xor1 = arr[0];                       
                                   
                                                 /* Get the xor of all array elements */                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 xor1 = xor1 ^ arr[i];                       
                                   
                                                 /* XOR the previous result with numbers                       
                                                 from 1 to n*/                       
                                                 for                                     (i = 1; i <= n; i++)                       
                                                 xor1 = xor1 ^ i;                       
                                   
                                                 /* Get the rightmost set bit in set_bit_no */                       
                                                 set_bit_no = xor1 & ~(xor1 - 1);                       
                                   
                                                 /* Now divide elements into two                       
                                                 sets by comparing a rightmost set                       
                                                 bit of xor1 with the bit at the same                       
                                                 position in each element. Also,                       
                                                 get XORs of two sets. The two                       
                                                 XORs are the output elements.                       
                                                 The following two for loops                       
                                                 serve the purpose */                       
                                                 for                                     (i = 0; i < n; i++) {                       
                                                 if                                     (arr[i] & set_bit_no)                       
                                                 /* arr[i] belongs to first set */                       
                                                 *x = *x ^ arr[i];                       
                                   
                                                 else                       
                                                 /* arr[i] belongs to second set*/                       
                                                 *y = *y ^ arr[i];                       
                                                 }                       
                                                 for                                     (i = 1; i <= n; i++) {                       
                                                 if                                     (i & set_bit_no)                       
                                                 /* i belongs to first set */                       
                                                 *x = *x ^ i;                       
                                   
                                                 else                       
                                                 /* i belongs to second set*/                       
                                                 *y = *y ^ i;                       
                                                 }                       
                                   
                                                 /* *x and *y hold the desired                       
                                                 output elements */                       
                         }                       
                                   
                         /* Driver code */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 3, 4, 5, 5, 6, 2 };                       
                                                 int                                     * x = (                                     int                                     *)                                     malloc                                     (                                     sizeof                                     (                                     int                                     ));                       
                                                 int                                     * y = (                                     int                                     *)                                     malloc                                     (                                     sizeof                                     (                                     int                                     ));                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                   
                                                 getTwoElements(arr, n, x, y);                       
                                                 cout <<                                     " The missing element is "                                     << *x <<                                     " and the repeating"                       
                                                 <<                                     " number is "                                     << *y;                       
                                                 getchar                                     ();                       
                         }                       
                                   
                         // This code is contributed by Code_Mech                       

C

                         // C program to Find the repeating                       
                         // and missing elements                       
                                   
                         #include <stdio.h>                       
                         #include <stdlib.h>                       
                                   
                         /* The output of this function is stored at                       
                                                 *x and *y */                       
                         void                                     getTwoElements(                                     int                                     arr[],                                     int                                     n,                                     int                                     * x,                                     int                                     * y)                       
                         {                       
                                                 /* Will hold xor of all elements and numbers                       
                                                 from 1 to n */                       
                                                 int                                     xor1;                       
                                   
                                                 /* Will have only single set bit of xor1 */                       
                                                 int                                     set_bit_no;                       
                                   
                                                 int                                     i;                       
                                                 *x = 0;                       
                                                 *y = 0;                       
                                   
                                                 xor1 = arr[0];                       
                                   
                                                 /* Get the xor of all array elements */                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 xor1 = xor1 ^ arr[i];                       
                                   
                                                 /* XOR the previous result with numbers                       
                                                 from 1 to n*/                       
                                                 for                                     (i = 1; i <= n; i++)                       
                                                 xor1 = xor1 ^ i;                       
                                   
                                                 /* Get the rightmost set bit in set_bit_no */                       
                                                 set_bit_no = xor1 & ~(xor1 - 1);                       
                                   
                                                 /* Now divide elements in two sets by comparing                       
                                                 rightmost set bit of xor1 with bit at same                       
                                                 position in each element. Also, get XORs of two                       
                                                 sets. The two XORs are the output elements. The                       
                                                 following two for loops serve the purpose */                       
                                                 for                                     (i = 0; i < n; i++) {                       
                                                 if                                     (arr[i] & set_bit_no)                       
                                                 /* arr[i] belongs to first set */                       
                                                 *x = *x ^ arr[i];                       
                                   
                                                 else                       
                                                 /* arr[i] belongs to second set*/                       
                                                 *y = *y ^ arr[i];                       
                                                 }                       
                                                 for                                     (i = 1; i <= n; i++) {                       
                                                 if                                     (i & set_bit_no)                       
                                                 /* i belongs to first set */                       
                                                 *x = *x ^ i;                       
                                   
                                                 else                       
                                                 /* i belongs to second set*/                       
                                                 *y = *y ^ i;                       
                                                 }                       
                                   
                                                 /* *x and *y hold the desired output elements */                       
                         }                       
                                   
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 3, 4, 5, 5, 6, 2 };                       
                                                 int                                     * x = (                                     int                                     *)                                     malloc                                     (                                     sizeof                                     (                                     int                                     ));                       
                                                 int                                     * y = (                                     int                                     *)                                     malloc                                     (                                     sizeof                                     (                                     int                                     ));                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                   
                                                 getTwoElements(arr, n, x, y);                       
                                                 printf                                     (                                     " The missing element is %d"                       
                                                 " and the repeating number"                       
                                                 " is %d"                                     ,                       
                                                 *x, *y);                       
                                                 getchar                                     ();                       
                         }                       

JAVA

                         // Java program to Find the repeating                       
                         // and missing elements                       
                                   
                         import                                     java.io.*;                       
                                   
                         class                                     GFG {                       
                                                 static                                     int                                     x, y;                       
                                   
                                                 static                                     void                                     getTwoElements(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 /* Will hold xor of all elements                       
                                                 and numbers from 1 to n  */                       
                                                 int                                     xor1;                       
                                   
                                                 /* Will have only single set bit of xor1 */                       
                                                 int                                     set_bit_no;                       
                                   
                                                 int                                     i;                       
                                                 x =                                     0                                     ;                       
                                                 y =                                     0                                     ;                       
                                   
                                                 xor1 = arr[                                     0                                     ];                       
                                   
                                                 /* Get the xor of all array elements  */                       
                                                 for                                     (i =                                     1                                     ; i < n; i++)                       
                                                 xor1 = xor1 ^ arr[i];                       
                                   
                                                 /* XOR the previous result with numbers from                       
                                                 1 to n*/                       
                                                 for                                     (i =                                     1                                     ; i <= n; i++)                       
                                                 xor1 = xor1 ^ i;                       
                                   
                                                 /* Get the rightmost set bit in set_bit_no */                       
                                                 set_bit_no = xor1 & ~(xor1 -                                     1                                     );                       
                                   
                                                 /* Now divide elements into two sets by comparing                       
                                                 rightmost set bit of xor1 with the bit at the same                       
                                                 position in each element. Also, get XORs of two                       
                                                 sets. The two XORs are the output elements. The                       
                                                 following two for loops serve the purpose */                       
                                                 for                                     (i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     ((arr[i] & set_bit_no) !=                                     0                                     )                       
                                                 /* arr[i] belongs to first set */                       
                                                 x = x ^ arr[i];                       
                                   
                                                 else                       
                                                 /* arr[i] belongs to second set*/                       
                                                 y = y ^ arr[i];                       
                                                 }                       
                                                 for                                     (i =                                     1                                     ; i <= n; i++) {                       
                                                 if                                     ((i & set_bit_no) !=                                     0                                     )                       
                                                 /* i belongs to first set */                       
                                                 x = x ^ i;                       
                                   
                                                 else                       
                                                 /* i belongs to second set*/                       
                                                 y = y ^ i;                       
                                                 }                       
                                   
                                                 /* *x and *y hold the desired output elements */                       
                                                 }                       
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     1                                     ,                                     6                                     ,                                     2                                     };                       
                                   
                                                 int                                     n = arr.length;                       
                                                 getTwoElements(arr, n);                       
                                                 System.out.println(                                     " The missing element is  "                       
                                                 + x +                                     "and the "                       
                                                 +                                     "repeating number is "                       
                                                 + y);                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Gitanjali.                       

Python3

                         # Python3 program to find the repeating                       
                         # and missing elements                       
                                   
                         # The output of this function is stored                       
                         # at x and y                       
                         def                                     getTwoElements(arr, n):                       
                                   
                                                 global                                     x, y                       
                                                 x                                     =                                     0                       
                                                 y                                     =                                     0                       
                                   
                                                 # Will hold xor of all elements                       
                                                 # and numbers from 1 to n                       
                                                 xor1                                     =                                     arr[                                     0                                     ]                       
                                   
                                                 # Get the xor of all array elements                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 xor1                                     =                                     xor1 ^ arr[i]                       
                                   
                                                 # XOR the previous result with numbers                       
                                                 # from 1 to n                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 xor1                                     =                                     xor1 ^ i                       
                                   
                                                 # Will have only single set bit of xor1                       
                                                 set_bit_no                                     =                                     xor1 & ~(xor1                                     -                                     1                                     )                       
                                   
                                                 # Now divide elements into two                       
                                                 # sets by comparing a rightmost set                       
                                                 # bit of xor1 with the bit at the same                       
                                                 # position in each element. Also,                       
                                                 # get XORs of two sets. The two                       
                                                 # XORs are the output elements.                       
                                                 # The following two for loops                       
                                                 # serve the purpose                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     (arr[i] & set_bit_no) !                                     =                                     0                                     :                       
                                   
                                                 # arr[i] belongs to first set                       
                                                 x                                     =                                     x ^ arr[i]                       
                                                 else                                     :                       
                                   
                                                 # arr[i] belongs to second set                       
                                                 y                                     =                                     y ^ arr[i]                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 if                                     (i & set_bit_no) !                                     =                                     0                                     :                       
                                   
                                                 # i belongs to first set                       
                                                 x                                     =                                     x ^ i                       
                                                 else                                     :                       
                                   
                                                 # i belongs to second set                       
                                                 y                                     =                                     y ^ i                       
                                   
                                                 # x and y hold the desired                       
                                                 # output elements                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     5                                     ,                                     6                                     ,                                     2                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                                   
                         getTwoElements(arr, n)                       
                                   
                         print                                     (                                     "The missing element is"                                     , x,                       
                                                 "and the repeating number is"                                     , y)                       
                                   
                         # This code is contributed by stutipathak31jan                       

C#

                         // C# program to Find the repeating                       
                         // and missing elements                       
                                   
                         using                                     System;                       
                                   
                         class                                     GFG {                       
                                                 static                                     int                                     x, y;                       
                                   
                                                 static                                     void                                     getTwoElements(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 /* Will hold xor of all elements                       
                                                 and numbers from 1 to n */                       
                                                 int                                     xor1;                       
                                   
                                                 /* Will have only single set bit of xor1 */                       
                                                 int                                     set_bit_no;                       
                                   
                                                 int                                     i;                       
                                                 x = 0;                       
                                                 y = 0;                       
                                   
                                                 xor1 = arr[0];                       
                                   
                                                 /* Get the xor of all array elements */                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 xor1 = xor1 ^ arr[i];                       
                                   
                                                 /* XOR the previous result with numbers from                       
                                                 1 to n*/                       
                                                 for                                     (i = 1; i <= n; i++)                       
                                                 xor1 = xor1 ^ i;                       
                                   
                                                 /* Get the rightmost set bit in set_bit_no */                       
                                                 set_bit_no = xor1 & ~(xor1 - 1);                       
                                   
                                                 /* Now divide elements in two sets by comparing                       
                                                 rightmost set bit of xor1 with bit at same                       
                                                 position in each element. Also, get XORs of two                       
                                                 sets. The two XORs are the output elements.The                       
                                                 following two for loops serve the purpose */                       
                                                 for                                     (i = 0; i < n; i++) {                       
                                                 if                                     ((arr[i] & set_bit_no) != 0)                       
                                   
                                                 /* arr[i] belongs to first set */                       
                                                 x = x ^ arr[i];                       
                                   
                                                 else                       
                                   
                                                 /* arr[i] belongs to second set*/                       
                                                 y = y ^ arr[i];                       
                                                 }                       
                                                 for                                     (i = 1; i <= n; i++) {                       
                                                 if                                     ((i & set_bit_no) != 0)                       
                                   
                                                 /* i belongs to first set */                       
                                                 x = x ^ i;                       
                                   
                                                 else                       
                                   
                                                 /* i belongs to second set*/                       
                                                 y = y ^ i;                       
                                                 }                       
                                   
                                                 /* *x and *y hold the desired output elements */                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 1, 3, 4, 5, 1, 6, 2 };                       
                                   
                                                 int                                     n = arr.Length;                       
                                                 getTwoElements(arr, n);                       
                                                 Console.Write(                                     " The missing element is "                       
                                                 + x +                                     "and the "                       
                                                 +                                     "repeating number is "                       
                                                 + y);                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to Find the repeating                       
                         // and missing elements                       
                                   
                         function                                     getTwoElements(&                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 /* Will hold xor of all elements                       
                                                 and numbers from 1 to n */                       
                                                 $xor1                                     ;                       
                                   
                                                 /* Will have only single set bit of xor1 */                       
                                                 $set_bit_no                                     ;                       
                                   
                                                 $i                                     ;                       
                                                 $x                                     = 0;                       
                                                 $y                                     = 0;                       
                                   
                                                 $xor1                                     =                                     $arr                                     [0];                       
                                   
                                                 /* Get the xor of all array elements */                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $xor1                                     =                                     $xor1                                     ^                                     $arr                                     [                                     $i                                     ];                       
                                   
                                                 /* XOR the previous result with numbers                       
                                                 from 1 to n*/                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 $xor1                                     =                                     $xor1                                     ^                                     $i                                     ;                       
                                   
                                                 /* Get the rightmost set bit in set_bit_no */                       
                                                 $set_bit_no                                     =                                     $xor1                                     & ~(                                     $xor1                                     - 1);                       
                                   
                                                 /* Now divide elements in two sets by comparing                       
                                                 rightmost set bit of xor1 with bit at same                       
                                                 position in each element. Also, get XORs of two                       
                                                 sets. The two XORs are the output elements.The                       
                                                 following two for loops serve the purpose */                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     ((                                     $arr                                     [                                     $i                                     ] &                                     $set_bit_no                                     ) != 0)                       
                                   
                                                 /* arr[i] belongs to first set */                       
                                                 $x                                     =                                     $x                                     ^                                     $arr                                     [                                     $i                                     ];                       
                                   
                                                 else                       
                                   
                                                 /* arr[i] belongs to second set*/                       
                                                 $y                                     =                                     $y                                     ^                                     $arr                                     [                                     $i                                     ];                       
                                                 }                       
                                   
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     ((                                     $i                                     &                                     $set_bit_no                                     ) != 0)                       
                                   
                                                 /* i belongs to first set */                       
                                                 $x                                     =                                     $x                                     ^                                     $i                                     ;                       
                                   
                                                 else                       
                                   
                                                 /* i belongs to second set*/                       
                                                 $y                                     =                                     $y                                     ^                                     $i                                     ;                       
                                                 }                       
                                   
                                                 /* *x and *y hold the desired output elements */                       
                                                 echo                                     (                                     "The missing element is "                                     .                                     $x                                     .                       
                                                 " and the repeating number is "                                     .                                     $y                                     );                       
                         }                       
                                   
                         // Driver Code                       
                         $arr                                     =                                     array                                     ( 1, 3, 4, 5, 1, 6, 2 );                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         getTwoElements(                                     $arr                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by Code_Mech                       

输出

 The missing element is 7 and the repeating number is 5

时间复杂性： O（n）这种方法不会导致溢出，但它不能判断哪一个出现两次，哪一个丢失。我们可以再增加一个步骤来检查哪一个缺失，哪一个重复。这很容易在O（n）时间内完成。

方法6（使用地图） 方法： 这个方法需要在Map的帮助下创建一个哈希表。在这种情况下，元素被映射到它们的自然索引。在这个过程中，如果一个元素被映射两次，那么它就是重复元素。如果一个元素的映射不存在，那么它就是缺少的元素。

以下是上述方法的实施情况：

C++

                         // C++ program to find the repeating                       
                         // and missing elements using Maps                       
                         #include <iostream>                       
                         #include <unordered_map>                       
                         using                                     namespace                                     std;                       
                                   
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 4, 3, 6, 2, 1, 1 };                       
                                                 int                                     n = 6;                       
                                   
                                                 unordered_map<                                     int                                     ,                                     bool                                     > numberMap;                       
                                   
                                                 for                                     (                                     int                                     i : arr)                       
                                                 {                       
                                                 if                                     (numberMap.find(i) ==                       
                                                 numberMap.end())                       
                                                 {                       
                                                 numberMap[i] =                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 cout <<                                     "Repeating = "                                     << i;                       
                                                 }                       
                                                 }                       
                                                 cout << endl;                       
                                   
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 if                                     (numberMap.find(i) ==                       
                                                 numberMap.end())                       
                                                 {                       
                                                 cout <<                                     "Missing = "                                     << i;                       
                                                 }                       
                                                 }                       
                                                 return                                     0;                       
                         }                       
                                   
                         // This code is contributed by RohitOberoi                       

JAVA

                         // Java program to find the                       
                         // repeating and missing elements                       
                         // using Maps                       
                                   
                         import                                     java.util.*;                       
                                   
                         public                                     class                                     Test1 {                       
                                   
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                   
                                                 int                                     [] arr = {                                     4                                     ,                                     3                                     ,                                     6                                     ,                                     2                                     ,                                     1                                     ,                                     1                                     };                       
                                   
                                                 Map<Integer, Boolean> numberMap                       
                                                 =                                     new                                     HashMap<>();                       
                                   
                                                 int                                     max = arr.length;                       
                                   
                                                 for                                     (Integer i : arr) {                       
                                   
                                                 if                                     (numberMap.get(i) ==                                     null                                     ) {                       
                                                 numberMap.put(i,                                     true                                     );                       
                                                 }                       
                                                 else                                     {                       
                                                 System.out.println(                                     "Repeating = "                                     + i);                       
                                                 }                       
                                                 }                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= max; i++) {                       
                                                 if                                     (numberMap.get(i) ==                                     null                                     ) {                       
                                                 System.out.println(                                     "Missing = "                                     + i);                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       

Python3

                         # Python3 program to find the                       
                         # repeating and missing elements                       
                         # using Maps                       
                         def                                     main():                       
                                   
                                                 arr                                     =                                     [                                     4                                     ,                                     3                                     ,                                     6                                     ,                                     2                                     ,                                     1                                     ,                                     1                                     ]                       
                                   
                                                 numberMap                                     =                                     {}                       
                                   
                                                 max                                     =                                     len                                     (arr)                       
                                                 for                                     i                                     in                                     arr:                       
                                                 if                                     not                                     i                                     in                                     numberMap:                       
                                                 numberMap[i]                                     =                                     True                       
                                   
                                                 else                                     :                       
                                                 print                                     (                                     "Repeating ="                                     , i)                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,                                     max                                     +                                     1                                     ):                       
                                                 if                                     not                                     i                                     in                                     numberMap:                       
                                                 print                                     (                                     "Missing ="                                     , i)                       
                         main()                       
                                   
                         # This code is contributed by stutipathak31jan                       

C#

                         // C# program to find the                       
                         // repeating and missing elements                       
                         // using Maps                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                                   
                         class                                     GFG                       
                         {                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     [] arr = { 4, 3, 6, 2, 1, 1 };                       
                                   
                                                 Dictionary<                                     int                                     , Boolean> numberMap =                       
                                                 new                                     Dictionary<                                     int                                     , Boolean>();                       
                                   
                                                 int                                     max = arr.Length;                       
                                   
                                                 foreach                                     (                                     int                                     i                                     in                                     arr)                       
                                                 {                       
                                                 if                                     (!numberMap.ContainsKey(i))                       
                                                 {                       
                                                 numberMap.Add(i,                                     true                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 Console.WriteLine(                                     "Repeating = "                                     + i);                       
                                                 }                       
                                                 }                       
                                                 for                                     (                                     int                                     i = 1; i <= max; i++)                       
                                                 {                       
                                                 if                                     (!numberMap.ContainsKey(i))                       
                                                 {                       
                                                 Console.WriteLine(                                     "Missing = "                                     + i);                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by PrinciRaj1992                       

输出

Repeating = 1
Missing = 5

方法7（使用平方和和和建立两个方程） 方法：

设x为缺失元素，y为重复元素。
设N是数组的大小。
使用公式得到所有数字的总和 S=N（N+1）/2
使用公式计算所有数字的平方和 Sum_Sq=N（N+1）（2N+1）/6
从i=1开始迭代循环…。N
S-=A[i]
Sum_Sq-=（A[i]*A[i]）
它将给出两个等式 x-y=S–（1） x^2–y^2=平方和 x+y=（总面积）–（2）

时间复杂性： O（n）

C++

                         #include <bits/stdc++.h>                       
                                   
                         using                                     namespace                                     std;                       
                                   
                         vector<                                     int                                     >repeatedNumber(                                     const                                     vector<                                     int                                     > &A) {                       
                                                 long                                     long                                     int                                     len = A.size();                       
                                                 long                                     long                                     int                                     Sum_N = (len * (len+1) ) /2, Sum_NSq = (len * (len +1) *(2*len +1) )/6;                       
                                                 long                                     long                                     int                                     missingNumber=0, repeating=0;                       
                                   
                                                 for                                     (                                     int                                     i=0;i<A.size(); i++){                       
                                                 Sum_N -= (                                     long                                     long                                     int                                     )A[i];                       
                                                 Sum_NSq -= (                                     long                                     long                                     int                                     )A[i]*(                                     long                                     long                                     int                                     )A[i];                       
                                                 }                       
                                   
                                                 missingNumber = (Sum_N + Sum_NSq/Sum_N)/2;                       
                                                 repeating= missingNumber - Sum_N;                       
                                                 vector <                                     int                                     > ans;                       
                                                 ans.push_back(repeating);                       
                                                 ans.push_back(missingNumber);                       
                                                 return                                     ans;                       
                                   
                         }                       
                                   
                                   
                         int                                     main(                                     void                                     ){                       
                                                 std::vector<                                     int                                     > v = {4, 3, 6, 2, 1, 6,7};                       
                                                 vector<                                     int                                     > res = repeatedNumber(v);                       
                                                 for                                     (                                     int                                     x: res){                       
                                                 cout<< x<<                                     "  "                                     ;                       
                                                 }                       
                                                 cout<<endl;                       
                         }                       

JAVA

                         import                                     java.util.*;                       
                         import                                     java.math.BigInteger;                       
                         class                                     GFG                       
                         {                       
                                                 static                                     Vector<Integer> repeatedNumber(                                     int                                     [] a)                       
                                                 {                       
                                   
                                                 BigInteger n=BigInteger.valueOf(a.length);                       
                                   
                                                 BigInteger s=BigInteger.valueOf(                                     0                                     );                       
                                                 BigInteger ss=BigInteger.valueOf(                                     0                                     );                       
                                   
                                                 for                                     (                                     int                                     x : a)                       
                                                 {                       
                                                 s=  s.add(BigInteger.valueOf(x));                       
                                                 ss= ss.add(BigInteger.valueOf(x).multiply(BigInteger.valueOf(x)));                       
                                                 }                       
                                   
                                                 BigInteger as= n.multiply(n.add(BigInteger.valueOf(                                     1                                     ))).divide(BigInteger.valueOf(                                     2                                     ));                       
                                                 BigInteger ass= as.multiply(BigInteger.valueOf(                                     2                                     ).multiply(n).add(BigInteger.valueOf(                                     1                                     ))).divide(BigInteger.valueOf(                                     3                                     ));                       
                                   
                                                 BigInteger sub=as.subtract(s);                       
                                                 BigInteger add=(ass.subtract(ss)).divide(sub);                       
                                                 //(ass-ss)/sub;                       
                                   
                                                 int                                     b = sub.add(add).divide(BigInteger.valueOf(                                     2                                     )).intValue();                       
                                                 //(sub+add)/2;                       
                                                 int                                     A = BigInteger.valueOf(b).subtract(sub).intValue();                       
                                                 Vector<Integer> ans =                                     new                                     Vector<>();                       
                                                 ans.add(A);                       
                                                 ans.add(b);                       
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     [] v = {                                     4                                     ,                                     3                                     ,                                     6                                     ,                                     2                                     ,                                     1                                     ,                                     6                                     ,                                     7                                     };                       
                                                 Vector<Integer> res = repeatedNumber(v);                       
                                                 for                                     (                                     int                                     x : res)                       
                                                 {                       
                                                 System.out.print(x +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Rajput-Ji                       

Python3

                         def                                     repeatedNumber(A):                       
                                   
                                                 length                                     =                                     len                                     (A)                       
                                                 Sum_N                                     =                                     (length                                     *                                     (length                                     +                                     1                                     ))                                     /                                     /                                     2                       
                                                 Sum_NSq                                     =                                     ((length                                     *                                     (length                                     +                                     1                                     )                                     *                       
                                                 (                                     2                                     *                                     length                                     +                                     1                                     ))                                     /                                     /                                     6                                     )                       
                                   
                                                 missingNumber, repeating                                     =                                     0                                     ,                                     0                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (A)):                       
                                                 Sum_N                                     -                                     =                                     A[i]                       
                                                 Sum_NSq                                     -                                     =                                     A[i]                                     *                                     A[i]                       
                                   
                                                 missingNumber                                     =                                     (Sum_N                                     +                                     Sum_NSq                                     /                                     /                       
                                                 Sum_N)                                     /                                     /                                     2                       
                                                 repeating                                     =                                     missingNumber                                     -                                     Sum_N                       
                                   
                                                 ans                                     =                                     []                       
                                                 ans.append(repeating)                       
                                                 ans.append(missingNumber)                       
                                   
                                                 return                                     ans                       
                                   
                         # Driver code                       
                         v                                     =                                     [                                     4                                     ,                                     3                                     ,                                     6                                     ,                                     2                                     ,                                     1                                     ,                                     6                                     ,                                     7                                     ]                       
                         res                                     =                                     repeatedNumber(v)                       
                                   
                         for                                     i                                     in                                     res:                       
                                                 print                                     (i, end                                     =                                     " "                                     )                       
                                   
                         # This code is contributed by stutipathak31jan                       

C#

                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                                   
                         class                                     GFG                       
                         {                       
                                                 static                                     List<                                     int                                     > repeatedNumber(                                     int                                     [] A)                       
                                                 {                       
                                                 int                                     len = A.Length;                       
                                                 int                                     Sum_N = (len * (len + 1)) / 2;                       
                                                 int                                     Sum_NSq = (len * (len + 1) *                       
                                                 (2 * len + 1)) / 6;                       
                                                 int                                     missingNumber = 0, repeating = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < A.Length; i++)                       
                                                 {                       
                                                 Sum_N -= A[i];                       
                                                 Sum_NSq -= A[i] * A[i];                       
                                                 }                       
                                   
                                                 missingNumber = (Sum_N + Sum_NSq /                       
                                                 Sum_N) / 2;                       
                                                 repeating = missingNumber - Sum_N;                       
                                                 List<                                     int                                     > ans =                                     new                                     List<                                     int                                     >();                       
                                                 ans.Add(repeating);                       
                                                 ans.Add(missingNumber);                       
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     [] v = { 4, 3, 6, 2, 1, 6, 7 };                       
                                                 List<                                     int                                     > res = repeatedNumber(v);                       
                                                 foreach                                     (                                     int                                     x                                     in                                     res)                       
                                                 {                       
                                                 Console.Write(x +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by PrinciRaj1992                       

输出

6  5

如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。

方法8（使用OR运算符）：

幸亏 安妮什·沙哈 感谢你提出这种方法。

方法：

给定一个输入数组

在输入数组上执行或操作。

同时，通过确定位置是否已设置，检查之前是否出现过该数字。我们将在这一步中获得重复编号。

要找到缺少的值，我们必须再次使用或检查包含0的位。

C++

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         int                                     main()                       
                         {                       
                                                 // Input:                       
                                                 vector<                                     int                                     > arr = {4, 3, 6, 2, 1, 1};                       
                                                 int                                     n = arr.size();                       
                                   
                                                 // Declaring output variables                       
                                                 // Note : arr[i]-1 is used instead of arr[i] as we want to use all 64 bits                       
                                                 int                                     bitOr = (1 << (arr[0]-1));                       
                                                 int                                     repeating, missing;                       
                                   
                                                 // Performing XOR as well as Checking repeating number                       
                                                 for                                     (                                     int                                     i=1; i<n; i++){                       
                                                 // If OR operation with 1 gives same output that means, we already have 1 at that position                       
                                                 if                                     ((bitOr | (1 << (arr[i]-1))) == bitOr) {                       
                                                 repeating = arr[i];                       
                                                 continue                                     ;                       
                                                 }                       
                                                 bitOr = (bitOr | (1 << (arr[i]-1)));                       
                                                 }                       
                                   
                                                 // Checking missing number                       
                                                 for                                     (                                     int                                     i=0; i<n; i++){                       
                                                 // property: OR with 0 yield 1 hence value of bitOr changes                       
                                                 if                                     ((bitOr | (1 << i)) != bitOr) {                       
                                                 missing = i+1;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 cout <<                                     "Repeating : "                                     << repeating <<                                     "Missing : "                                     << missing;                       
                                                 return                                     0;                       
                         }                       

输出

Repeating : 1
Missing : 5

时间复杂性 ：O（n） 辅助的 复杂性 ：O（1）

该方法的局限性 ：它只在机器上工作 数组大小<=64 如果我们使用长时间 数组大小<=32

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

THE END

技术文章