本文主要是介绍三个数是唯一出现的，其余的都出现偶数个，找出这三个数中。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：一个数组里，除了三个数是唯一出现的，其余的都出现偶数个，找出这三个数中。
比如数组元素为[1,1,2,2,3,3,4,5,6]，只有4,5,6这三个数字是唯一出现的，我们只需要输出4,5,6中的一个就行。
思路：
1.这个数组元素个数一定为奇数
假如有103个数，则有50对数，加上三个不同的数，则这三个和50对中的任何一个都不同。
2.因为3个数不相同， 三个数一定不可能每一bit位都相同。 如果每个bit位都相同，那么十进制的值也一定相等的。
我们可以找到其中一个数的bit位与其他两个不同，可以把那一个数从三个数字中分出来.
3.三个数肯定可以分到两组不同的数组里面去，基于这样的思路就可以找出这三个不同数字中的一个.
因为一位bit位只能区分两种状态，所以根据其中一个数的bit位与其他两个不同，可以把三个数中的二个分到一组，一个分到另一组。
下面用到异或的性质
1.A^A = 0 两个相同的数异或一定等于0
2. A^0 = A 任何数和0异或都等于0本身
比如数组元素为[1,1,2,2,3,3,4,5,6] 2的二进制是 010 ，3的二进制是011 ，如果按最后一位分，
最后一位是0在第一组，最后一位是1在第二组，那么两个2 一定都在第一组，两个3 一定都在另二组，然后
2^2 与3^3 的异或结果就都等于0. 0在与其他的单个数异或，结果就等于那个数了。
将找出的数和所有数异或，相当于又放入数组一个这个数， 这时候数组中就只有两个不同的数了。
考虑“只有两个数出现一次”的情况：可以找到一种方法，将数组划分为两部分，且让这两个数分别在不同部分，
这样每部分所有数的异或值，恰好分别等于这两个数。一种简单的分法就是，先计算出这两个数的异或值M（等价于求数组中所有数的异或值），
求出M值的二进制表示中的最低位1（其它位的1也可以，只不过麻烦点）在 第k位，然后根据第k位是否为1，将原数组分为两部分。
如4,5,6的二进制分别为0100,0101,0110。因为5的的倒数第一位为1，而其他的为0，程序第一个输出的就是5了。
程序如下：
#include<stdio.h>
#include<stdlib.h>#define bit(t,i) ( (t) & (1 << (i) ))
#define N 9
int findOneDif(int arr[], int len)
{int groupA, groupB, cntA, cntB, i, j;for (i = 0; i <= 31; i++){groupA = groupB = cntA = cntB = 0; //全部初始化为0for (j = 0; j < len; j++){if ( bit(arr[j], i)) //按倒数第i位分组,第i位为1在第一组，第i位为0在倒数第二组{groupA ^= arr[j];cntA++;}else{//groupB ^= arr[j];cntB++;}}if (cntA % 2 == 1 && groupB != 0) {//A组是奇数个元素,另外两个不同的数在B组(B组的异或值就不等于零)。printf("%d\n", groupA);return groupA;}if (cntB % 2 == 1 && groupA != 0){//B组是奇数个元素,另外两个不同的数在A组(A组的异或值就不等于零)。printf("%d\n", groupB);return groupB;}}
}int findLastBit1(int n)
{int i;for (i = 0; i < 32; i++){if (n & (1 << i)){return i;}}
}
int main()
{int arr[] = { 1,1,2,2,3,3,4,5,6 };int bit_pos,difNum, i,a_b, groupA, groupB, dist;difNum = findOneDif(arr, N); //找出一个出现一次的数,一会将找出的这个数和所有的数异或a_b = 0;for (i = 0; i < N; i++) //(相当于找出的这个数在数组中出现2次)结果就等于另外两个不同的数异或，{ //因为除了三个不同的数,其他的数异或结果本来就为零。a_b ^= arr[i];}a_b ^= difNum; //求出两个数的异或值bit_pos = findLastBit1(a_b); //找出异或结果最后一位不为1的位置，假设为k位dist = (1 << bit_pos); groupA = groupB = 0;for (i = 0; i < N; i++){if (arr[i] == difNum) //将数组中找的那一个不同的数排除掉continue;if (arr[i] & dist) //k位为1,分第一组 {groupA ^= arr[i];}else{ //k位为0,分第二组 groupB ^= arr[i];}}printf("%d %d %d\n", groupA, groupB, difNum);<span style="white-space:pre"> </span>//分出了三个数system("pause");
}这篇关于三个数是唯一出现的，其余的都出现偶数个，找出这三个数中。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
