找出数组中出现偶数次的两个数字

题目

已知一个数组中有大量的数字，其中很多数字出现了偶数次，只有两个数字出现了奇数次，请找出这两个数字。

解析

首先我们要学会从数组中找出一个奇数次的数字;
我们知道 a^a=0 , 0^a=a , 这组数字中只有两个没出现偶数次的数字，我们只要找到一定的方法把这两个数字分到不同的数组，再亦或求解即可。
如图所示分成这样的两组数字即可。

详细思路：
找出二进制中数字不同位；
按照位的不同进行分类；
分别亦或每个数组，求出数字；

代码

#define  _CRT_SECURE_NO_WARNINGS 1

//在一组数字中，有很多数字，但是只有两个数字出现了奇数次，求这两个数字。
#include
int main()
{
	//自测输入
	int arr[30];
	int num1 = 0;
	int num2 = 0;
	int i = 0;
	int count = 0;
	while (scanf("%d", &arr[i]))
	{
		i++;
		count++;
	}
	//开始寻找

	//找到不同这两个数字二进制不同的位
	int key = 0;
	int place = 0;
	for (i = 0; i < count; i++)
	{
		key ^= arr[i];
	}
	for (i = 0; !((key << i) & 1); i++)
	{
		;
	}
	place = i;
	for (i = 0; i < count; i++)
	{
		if ((arr[i] << place) & 1)
			num1 ^= arr[i];
		else
			num2 ^= arr[i];
	}
	printf("%d %d", num1, num2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

在这里我们用 key 表示所有数字亦或的结果；
用 place 表示二进制的哪一位不同。
让后每组数字进行亦或求解即可，得出答案

结果展示

总结

此题总体思路是，把不会的问题（一道题）拆解成我们学过的问题（相同的两道题），难点在于如何正确的进行两组数的划分。
希望大家多多支持与鼓励！