本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• C ++
• C
• Java
• Python3
• C#
• 的PHP

给定一个未排序的数组, 其中包含除两个数字以外的所有数字的偶数个出现次数。找出两个在O(n)时间复杂度和O(1)额外空间中出现奇数的数字。
例子：

Input: {12, 23, 34, 12, 12, 23, 12, 45}Output: 34 and 45Input: {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100}Output: 100 and 5000Input: {10, 20}Output: 10 and 20

推荐：请在"实践首先, 在继续解决方案之前。一种天真的方法解决此问题的方法是运行两个嵌套循环。外循环拾取一个元素, 内循环计数拾取的元素的出现次数。如果出现次数是奇数, 则打印数字。该方法的时间复杂度为O(n ^ 2)。
我们可以使用排序以获取O(nLogn)时间中出现的奇数。首先使用O(nLogn)排序算法(例如合并排序, 堆排序等)对数字进行排序。对数组进行排序后, 我们要做的就是对数组进行线性扫描并打印出现的奇数。
我们也可以使用哈希。创建一个空的哈希表, 其中将包含元素及其计数。一一挑选输入数组的所有元素。在哈希表中查找选择的元素。如果在哈希表中找到该元素, 则在表中增加其计数。如果找不到该元素, 则将其输入到哈希表中, 计数为1。将所有元素输入哈希表后, 扫描哈希表并打印具有奇数的元素。这种方法平均可能需要O(n)时间, 但需要O(n)额外空间。
O(n)时间和O(1)额外空间解决方案：
这个想法类似于
【如何找出在未排序数组中出现奇数的两个数字（）】这个
发布。令两个出现的奇数为x和y。我们
使用按位异或
得到x和y。
第一步是对数组中存在的所有元素进行XOR
。由于XOR运算的以下特性, 所有元素的XOR使我们对x和y进行XOR。
1)任何数字n与自身的XOR等于0, 即n ^ n = 0
2)任意数字n与0的XOR运算得到n, 即n ^ 0 = n
3)XOR是累积和关联的。
因此, 第一步之后, 我们对x和y进行了XOR。令XOR的值为xor2。 xor2中的每个置位指示x和y中的相应位具有彼此不同的值。例如, 如果x = 6(0110)并且y为15(1111), 则xor2将为(1001), xor2中的两个置位指示x和y中的相应位不同。
在第二步中, 我们选择xor2的一组位并将数组元素分成两组
。 x和y将进入不同的组。在下面的代码中, 选择xor2的最右边设置位是因为它很容易获得数字的最右边设置位。如果对数组中所有具有相应位(或1)的元素进行XOR, 则将得到第一个奇数。而且, 如果我们对所有具有对应位0的元素进行XOR, 那么我们将获得另一个奇数发生数。由于XOR具有相同的属性, 因此此步骤有效。一个数字的所有出现都将进入同一集合。对所有出现的偶数次出现的所有数字进行XOR运算, 其结果将为0。集合的异或将是奇数发生的元素之一。
C ++

// C++ Program to find the two odd occurring elements #include < bits/stdc++.h> using namespace std; /* Prints two numbers that occur odd number of times. The function assumes that the array size is at least 2 and there are exactly two numbers occurring odd number of times. */ void printTwoOdd( int arr[], int size) { int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */ int set_bit_no; /* Will have only single set bit of xor2 */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[]. The xor will basically be xor of two odd occurring elements */ for (i = 1; i < size; i++) xor2 = xor2 ^ arr[i]; /* Get one set bit in the xor2. We get rightmost set bit in the following line as it is easy to get */ set_bit_no = xor2 & ~(xor2-1); /* Now divide elements in two sets: 1) The elements having the corresponding bit as 1. 2) The elements having the corresponding bit as 0. */ for (i = 0; i < size; i++) { /* XOR of first set is finally going to hold one odd occurring number x */ if (arr[i] & set_bit_no) x = x ^ arr[i]; /* XOR of second set is finally going to hold the other odd occurring number y */ else y = y ^ arr[i]; } cout < < "The two ODD elements are " < < x < < " & " < < y; } /* Driver code */ int main() { int arr[] = {4, 2, 4, 5, 2, 3, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printTwoOdd(arr, arr_size); return 0; } // This is code is contributed by rathbhupendra

C

// Program to find the two odd occurring elements #include< stdio.h> /* Prints two numbers that occur odd number of times. The function assumes that the array size is at least 2 and there are exactly two numbers occurring odd number of times. */ void printTwoOdd( int arr[], int size) { int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */ int set_bit_no; /* Will have only single set bit of xor2 */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[]. The xor will basically be xor of two odd occurring elements */ for (i = 1; i < size; i++) xor2 = xor2 ^ arr[i]; /* Get one set bit in the xor2. We get rightmost set bit in the following line as it is easy to get */ set_bit_no = xor2 & ~(xor2-1); /* Now divide elements in two sets: 1) The elements having the corresponding bit as 1. 2) The elements having the corresponding bit as 0.*/ for (i = 0; i < size; i++) { /* XOR of first set is finally going to hold one odd occurring number x */ if (arr[i] & set_bit_no) x = x ^ arr[i]; /* XOR of second set is finally going to hold the other odd occurring number y */ else y = y ^ arr[i]; }printf ( "\n The two ODD elements are %d & %d " , x, y); }/* Driver program to test above function */ int main() { int arr[] = {4, 2, 4, 5, 2, 3, 3, 1}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printTwoOdd(arr, arr_size); getchar (); return 0; }

Java

// Java program to find two odd // occurring elementsimport java.util.*; class Main {/* Prints two numbers that occur odd number of times. The function assumes that the array size is at least 2 and there are exactly two numbers occurring odd number of times. */ static void printTwoOdd( int arr[], int size) { /* Will hold XOR of two odd occurring elements */ int xor2 = arr[ 0 ]; /* Will have only single set bit of xor2 */ int set_bit_no; int i; int n = size - 2 ; int x = 0 , y = 0 ; /* Get the xor of all elements in arr[]. The xor will basically be xor of two odd occurring elements */ for (i = 1 ; i < size; i++) xor2 = xor2 ^ arr[i]; /* Get one set bit in the xor2. We get rightmost set bit in the following line as it is easy to get */ set_bit_no = xor2 & ~(xor2- 1 ); /* Now divide elements in two sets: 1) The elements having the corresponding bit as 1. 2) The elements having the corresponding bit as 0.*/ for (i = 0 ; i < size; i++) { /* XOR of first set is finally going to hold one odd occurring number x */ if ((arr[i] & set_bit_no)> 0 ) x = x ^ arr[i]; /* XOR of second set is finally going to hold the other odd occurring number y */ else y = y ^ arr[i]; }System.out.println( "The two ODD elements are " + x + " & " + y); }// main function public static void main (String[] args) { int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 3 , 1 }; int arr_size = arr.length; printTwoOdd(arr, arr_size); } }

Python3

# Python3 program to find the # two odd occurring elements# Prints two numbers that occur odd # number of times. The function assumes # that the array size is at least 2 and # there are exactly two numbers occurring # odd number of times. def printTwoOdd(arr, size):# Will hold XOR of two odd occurring elements xor2 = arr[ 0 ] # Will have only single set bit of xor2 set_bit_no = 0 n = size - 2 x, y = 0 , 0# Get the xor of all elements in arr[]. # The xor will basically be xor of two # odd occurring elements for i in range ( 1 , size): xor2 = xor2 ^ arr[i]# Get one set bit in the xor2. We get # rightmost set bit in the following # line as it is easy to get set_bit_no = xor2 & ~(xor2 - 1 )# Now divide elements in two sets: # 1) The elements having the corresponding bit as 1. # 2) The elements having the corresponding bit as 0. for i in range (size):# XOR of first set is finally going to # hold one oddoccurring number x if (arr[i] & set_bit_no): x = x ^ arr[i]# XOR of second set is finally going # to hold the other odd occurring number y else : y = y ^ arr[i] print ( "The two ODD elements are" , x, "& " , y)# Driver Code arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 3 , 1 ] arr_size = len (arr) printTwoOdd(arr, arr_size)# This code is contributed by Anant Agarwal.

C#

// C# program to find two odd // occurring elements using System; class main {// Prints two numbers that occur // odd number of times. Function // assumes that array size is at // least 2 and there are exactly // two numbers occurring odd number // of times. static void printTwoOdd( int []arr, int size) {// Will hold XOR of two odd //occurring elements int xor2 = arr[0]; // Will have only single set // bit of xor2 int set_bit_no; int i; //int n = size - 2; int x = 0, y = 0; // Get the xor of all the elements // in arr[].The xor will basically // be xor of two odd occurring // elements for (i = 1; i < size; i++) xor2 = xor2 ^ arr[i]; // Get one set bit in the xor2. // We get rightmost set bit in // the following line as it is // to get. set_bit_no = xor2 & ~(xor2-1); // divide elements in two sets: // 1) The elements having the // corresponding bit as 1. // 2) The elements having the // corresponding bit as 0. for (i = 0; i < size; i++) { // XOR of first set is finally // going to hold one odd // occurring number x if ((arr[i] & set_bit_no)> 0) x = x ^ arr[i]; // XOR of second set is finally // going to hold the other // odd occurring number y else y = y ^ arr[i]; }Console.WriteLine( "The two ODD elements are " + x + " & " + y); }// main function public static void Main() { int []arr = {4, 2, 4, 5, 2, 3, 3, 1}; int arr_size = arr.Length; printTwoOdd(arr, arr_size); } }//This code is contributed by Anant Agarwal.

的PHP

< ?php // PHP program to find the // two odd occurring elements/* Prints two numbers that occur odd number of times. The function assumes that the array size is at least 2 and there are exactly two numbers occurring odd number of times. */ function printTwoOdd( $arr , $size ) {// Will hold XOR of two // odd occurring elements $xor2 = $arr [0]; // Will have only single // set bit of xor2 $set_bit_no ; $i ; $n = $size - 2; $x = 0; $y = 0; // Get the xor of all elements // in arr[]. The xor will basically // be xor of two odd occurring // elements for ( $i = 1; $i < $size ; $i ++) $xor2 = $xor2 ^ $arr [ $i ]; // Get one set bit in the xor2. // We get rightmost set bit // in the following line as // it is easy to get $set_bit_no = $xor2 & ~( $xor2 -1); /* Now divide elements in two sets: 1) The elements having the corresponding bit as 1. 2) The elements having the corresponding bit as 0. */ for ( $i = 0; $i < $size ; $i ++) {/* XOR of first set is finally going to hold one odd occurring number x */ if ( $arr [ $i ] & $set_bit_no ) $x = $x ^ $arr [ $i ]; /* XOR of second set is finally going to hold the other odd occurring number y */ else $y = $y ^ $arr [ $i ]; }echo "The two ODD elements are " , $x , " & " , $y ; }// Driver Code $arr = array (4, 2, 4, 5, 2, 3, 3, 1); $arr_size = sizeof( $arr ); printTwoOdd( $arr , $arr_size ); // This code is Contributed by Ajit ?>

输出如下：

The two ODD elements are 5 & 1

时间复杂度：O(n)
辅助空间：O(1)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  互联网销售数据分析
• 

  redis解决高并发问题,如商品秒杀 redis高并发架构与底层原理
• 

  tcl洗衣机快洗要多久 tcl洗衣机快速洗衣多久
• 

  销售是做什么的 销售具体是做什么的
• 

  缅甸红酸枝是红木吗
• 

  射击游戏最帅角色排行榜，射击游戏高手
• 

  adb push build.prop system 重启后无法进入系统解决方法
• 

  莆田本土“19+17”:含15名小学生
• 

  道声|道声 再见
• 

  哪些食物含有花青素 为什么鸡蛋和紫薯一起就变绿
• 

  DOTA2暗影萨满怎么玩 DOTA2小y技能介绍
• 

  sap现金管理与预算控制，erp现金管理
• 

  pdf阅读器的文字怎么粘贴复制
• 

  豁牙巴是什么意思 豁牙巴应该是什么意思
• 

  新冠疫苗|海口新增19个60岁及以上人群新冠疫苗接种点 老年人接种点达27个
• 

  健康码灰色几天能变绿
• 

  支付宝账户管理在哪
• 

  mongodb 集合内文档之间关联 mongodb 合并数据
• 

  儿童肾病综合症治疗方法首选 儿童肾病综合症治疗方法
• 

  管钳价格 「管钳什么牌子的最好」

• 如何设置Anaconda路径到环境变量（）
• SASS基本语法是怎么样的（）
• 如何实现Strassen的矩阵乘法算法（）
• 深入浅出（Linux文件层次结构详细指南和教程）
• 算法（如何实现求n范围内出现的最大整数-S2）
• Python中的hash()方法怎么使用（）
• JavaScript如何用多个其他字符串替换多个字符串（）
• 本图文详细教程教你win10怎样设置远程桌面连接
• 本图文详细教程教你处理win10开机慢