在有限范围内的数组中找到甚至出现的元素-yiteyi-C++库

给定一个数组，该数组包含除少数元素出现偶数次之外的所有数字的奇数次。在O（n）时间复杂度和O（1）额外空间中查找数组中偶数出现的元素。假设数组包含范围为0到63的元素。 例如：

null

Input: [9, 12, 23, 10, 12, 12, 15, 23, 14, 12, 15]Output: 12, 23 and 15Input: [1, 4, 7, 5, 9, 7, 3, 4, 6, 8, 3, 0, 3]Output: 4 and 7Input: [4, 4, 10, 10, 4, 4, 4, 4, 10, 10]Output: 4 and 10

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

一个简单的方法是遍历阵列，并将其元素的频率存储在地图中。之后，打印地图中的偶数元素。该解决方案需要O（n）时间，但需要额外的空间来存储频率。下面是一个使用位运算符解决此问题的有趣方法。此方法假定长整数使用64位存储。这个想法是使用XOR运算符。我们知道

1 XOR 1 = 01 XOR 0 = 10 XOR 1 = 10 XOR 0 = 0

考虑下面的输入-

 1, 4, 7, 5, 9, 7, 3, 4, 6, 8, 3, 0, 3

如果我们按数组中每个元素的值左移1，并对所有项取XOR，我们将得到二进制整数以下的值——

1101101011

右边第i个索引中的每个1代表元素i的奇数出现。右边第i个索引中的每个0代表元素i在数组中的偶数或不出现。 0出现在上述二进制数的第2、第4和第7位。但2在我们的阵列中不存在。所以我们的答案是4和7。下面是上述想法的实现

C++

                         // C++ Program to find the even occurring elements                       
                         // in given array                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find the even occurring elements                       
                         // in given array                       
                         void                                     printRepeatingEven(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 long                                     long                                     _xor = 0L;                       
                                                 long                                     long                                     pos;                       
           
                                                 // do for each element of array                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of current element                       
                                                 pos = 1 << arr[i];                       
           
                                                 // Toggle the bit everytime element gets repeated                       
                                                 _xor ^= pos;                       
                                                 }                       
           
                                                 // Traverse array again and use _xor to find even                       
                                                 // occurring elements                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of current element                       
                                                 pos = 1 << arr[i];                       
           
                                                 // Each 0 in _xor represents an even occurrence                       
                                                 if                                     (!(pos & _xor))                       
                                                 {                       
                                                 // print the even occurring numbers                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
           
                                                 // set bit as 1 to avoid printing duplicates                       
                                                 _xor ^= pos;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 9, 12, 23, 10, 12, 12, 15, 23,                       
                                                 14, 12, 15 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 printRepeatingEven(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find the even occurring                       
                         // elements in given array                       
                         class                                     GFG                       
                         {                       
           
                         // Function to find the even occurring                       
                         // elements in given array                       
                         static                                     void                                     printRepeatingEven(                                     int                                     arr[],                       
                                                 int                                     n)                       
                         {                       
                                                 long                                     _xor = 0L;                       
                                                 long                                     pos;                       
           
                                                 // do for each element of array                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of                       
                                                 // current element                       
                                                 pos =                                     1                                     << arr[i];                       
           
                                                 // Toggle the bit everytime                       
                                                 // element gets repeated                       
                                                 _xor ^= pos;                       
                                                 }                       
           
                                                 // Traverse array again and use _xor                       
                                                 // to find even occurring elements                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of                       
                                                 // current element                       
                                                 pos =                                     1                                     << arr[i];                       
           
                                                 // Each 0 in _xor represents                       
                                                 // an even occurrence                       
                                                 if                                     (!((pos & _xor)!=                                     0                                     ))                       
                                                 {                       
                                                 // print the even occurring numbers                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
           
                                                 // set bit as 1 to avoid                       
                                                 // printing duplicates                       
                                                 _xor ^= pos;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String args[])                       
                         {                       
                                                 int                                     arr[] = {                                     9                                     ,                                     12                                     ,                                     23                                     ,                                     10                                     ,                                     12                                     ,                                     12                                     ,                       
                                                 15                                     ,                                     23                                     ,                                     14                                     ,                                     12                                     ,                                     15                                     };                       
                                                 int                                     n = arr.length;                       
           
                                                 printRepeatingEven(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by 29AjayKumar                       

C#

                         // C# Program to find the even occurring                       
                         // elements in given array                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to find the even occurring                       
                         // elements in given array                       
                         static                                     void                                     printRepeatingEven(                                     int                                     [] arr,                       
                                                 int                                     n)                       
                         {                       
                                                 long                                     _xor = 0L;                       
                                                 long                                     pos;                       
           
                                                 // do for each element of array                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of                       
                                                 // current element                       
                                                 pos = 1 << arr[i];                       
           
                                                 // Toggle the bit everytime                       
                                                 // element gets repeated                       
                                                 _xor ^= pos;                       
                                                 }                       
           
                                                 // Traverse array again and use _xor                       
                                                 // to find even occurring elements                       
                                                 for                                     (                                     int                                     i = 0; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of                       
                                                 // current element                       
                                                 pos = 1 << arr[i];                       
           
                                                 // Each 0 in _xor represents                       
                                                 // an even occurrence                       
                                                 if                                     (!((pos & _xor) != 0))                       
                                                 {                       
                                                 // print the even occurring numbers                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
           
                                                 // set bit as 1 to avoid                       
                                                 // printing duplicates                       
                                                 _xor ^= pos;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     [] arr = {9, 12, 23, 10, 12, 12,                       
                                                 15, 23, 14, 12, 15};                       
                                                 int                                     n = arr.Length;                       
           
                                                 printRepeatingEven(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Mukul singh                       

PHP

                         <?php                       
                         // PHP Program to find the even                       
                         // occurring elements in given array                       
           
                         // Function to find the even                       
                         // occurring elements in given array                       
                         function                                     printRepeatingEven(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $_xor                                     = 0;                       
                                                 $pos                                     ;                       
           
                                                 // do for each element of array                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ; ++                                     $i                                     )                       
                                                 {                       
                                                 // left-shift 1 by value                       
                                                 // of current element                       
                                                 $pos                                     = 1 <<                                     $arr                                     [                                     $i                                     ];                       
           
                                                 // Toggle the bit everytime                       
                                                 // element gets repeated                       
                                                 $_xor                                     ^=                                     $pos                                     ;                       
                                                 }                       
           
                                                 // Traverse array again and                       
                                                 // use _xor to find even                       
                                                 // occurring elements                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ; ++                                     $i                                     )                       
                                                 {                       
                                                 // left-shift 1 by value                       
                                                 // of current element                       
                                                 $pos                                     = 1 <<                                     $arr                                     [                                     $i                                     ];                       
           
                                                 // Each 0 in _xor represents                       
                                                 // an even occurrence                       
                                                 if                                     (!(                                     $pos                                     &                                     $_xor                                     ))                       
                                                 {                       
                                                 // print the even                       
                                                 // occurring numbers                       
                                                 echo                                     $arr                                     [                                     $i                                     ],                                     " "                                     ;                       
           
                                                 // set bit as 1 to avoid                       
                                                 // printing duplicates                       
                                                 $_xor                                     ^=                                     $pos                                     ;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (9, 12, 23, 10, 12, 12,                       
                                                 15, 23, 14, 12, 15 );                       
                         $n                                     = sizeof(                                     $arr                                     );                       
           
                         printRepeatingEven(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by aj_36                       
                         ?>                       

Python 3

                         # Python 3 program to find the even                       
                         # occurring elements in given array                       
           
                         # Function to find the even occurring                       
                         # elements in given array                       
                         def                                     printRepeatingEven(arr, n):                       
           
                                                 axor                                     =                                     0                                     ;                       
           
                                                 # do for each element of array                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                   
                                                 # left-shift 1 by value of                       
                                                 # current element                       
                                                 pos                                     =                                     1                                     << arr[i];                       
           
                                                 # Toggle the bit every time                       
                                                 # element gets repeated                       
                                                 axor ^                                     =                                     pos;                       
                                   
                                                 # Traverse array again and use _xor                       
                                                 # to find even occurring elements                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     -                                     1                                     ):                       
                                   
                                                 # left-shift 1 by value of                       
                                                 # current element                       
                                                 pos                                     =                                     1                                     << arr[i];                       
           
                                                 # Each 0 in _xor represents an                       
                                                 # even occurrence                       
                                                 if                                     (                                     not                                     (pos & axor)):                       
                                   
                                                 # print the even occurring numbers                       
                                                 print                                     (arr[i], end                                     =                                     " "                                     );                       
           
                                                 # set bit as 1 to avoid printing                       
                                                 # duplicates                       
                                                 axor ^                                     =                                     pos;                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     9                                     ,                                     12                                     ,                                     23                                     ,                                     10                                     ,                                     12                                     ,                                     12                                     ,                       
                                                 15                                     ,                                     23                                     ,                                     14                                     ,                                     12                                     ,                                     15                                     ];                       
                         n                                     =                                     len                                     (arr) ;                       
                         printRepeatingEven(arr, n);                       
           
                         # This code is contributed                       
                         # by Shivi_Aggarwal                       

Javascript

                         <script>                       
           
                         // Javascript Program to find the even occurring                       
                         // elements in given array                       
           
                         // Function to find the even occurring                       
                         // elements in given array                       
                         function                                     printRepeatingEven(arr, n)                       
                         {                       
                                                 let _xor = 0;                       
                                                 let pos;                       
                                   
                                                 // do for each element of array                       
                                                 for                                     (let i = 0; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of                       
                                                 // current element                       
                                                 pos = 1 << arr[i];                       
                                   
                                                 // Toggle the bit everytime                       
                                                 // element gets repeated                       
                                                 _xor ^= pos;                       
                                                 }                       
                                   
                                                 // Traverse array again and use _xor                       
                                                 // to find even occurring elements                       
                                                 for                                     (let i = 0; i < n; ++i)                       
                                                 {                       
                                                 // left-shift 1 by value of                       
                                                 // current element                       
                                                 pos = 1 << arr[i];                       
                                   
                                                 // Each 0 in _xor represents                       
                                                 // an even occurrence                       
                                                 if                                     (!((pos & _xor)!=0))                       
                                                 {                       
                                                 // print the even occurring numbers                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                   
                                                 // set bit as 1 to avoid                       
                                                 // printing duplicates                       
                                                 _xor ^= pos;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                                   
                                                 let arr = [9, 12, 23, 10, 12, 12,                       
                                                 15, 23, 14, 12, 15];                       
                                                 let n = arr.length;                       
                                   
                                                 printRepeatingEven(arr, n);                       
                                   
                         </script>                       

输出：

12 23 15

时间复杂性： O（n）

辅助空间： O（1）

本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章