编程之美-----在一个整型数组里找出只出现过一次的那两个数

浏览数：49 / 时间：2015年06月08日

一、一个数组里除了一个数字之外，其他的数字都出现了两次

用异或来解

#include <iostream>
using namespace std;
int main()
{
    int T;
    int n,m;
    while(cin>>T,T){
        cin>>n;
       
        while(--T){
            cin>>m;
            n=m^n;              
       }
        printf("%d\n",n);
    }
    return 0;
}

扩展：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

http://www.cnblogs.com/youxin/p/3349834.html

数据： 1 2 1 3 5 3 4 6 5 6

解法：

1、用上面那个方法从s [0]开始一直与每个数进行异或，最后得到 n=6，（110)2

2、要把这个数组分成两个分别只含一个数（2或4）的数组，然后就好办了

原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。

3、怎么分？由于这两个数是不一样的，所以这个异或结果包含了这两个数的特征。把第一步异或的到的 n=6,（110）2 找到二进制位中为1的数分别做为一组。即：* 1* 和 10* 两组，那么就是分为：{ 3,3,2,6,6} 和 { 1,1,5,4,5}两组。怎么找？找到之后怎么分？

4、那么怎么处理才能进行分组呢？

//Test Case : int s[10]={1,2,1,3,5,3,4,6,5,6};
//函数功能 ： 找出数组中两个只出现一次的数字
//函数参数 ： arr为源数组，len为数组元素个数，result用来存放结果 
//返回值 ：   无
void FindIsolateTwo(int *arr, int len,int *result)
{
    //int len = sizeof(arr)/sizeof(arr[0]);
    result[0] = result[1] = 0;

    int i, all = 0, flag = 1;

    for(i = 0; i < len ; i++) //所有数异或
        all ^= arr[i];

    while(!(all&flag))  //寻找过滤位;(all&flag)非0就跳出
        flag <<= 1;

    
    for(i = 0; i < len; i++) //利用过滤位区分
    {
        if(flag&arr[i])
            result[0] ^= arr[i];
        else
            result[1] ^= arr[i];
    }
}