[剑指Offer]40.数组中只出现一次的数字

题目

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路

我们直到异或的性质:

任何一个数字异或他自己都等于0.

所以说我们如果从头到尾依次异或每一个数字,那么最终的结果刚好只出现一次的数字,因为成对出现的两次的数字全部在异或中抵消了。

这道题中有两个数字只出现一次。这样的话我们得到的结果就是这两个数字的异或结果。因此我们想办法把原数组分成两个子数组,使得每个子数组包含一个只出现一次的数字。这样我们就可以对这两个子数组分别异或,就能得到两个只出现一次的数字。

现在问题是怎样把原数组分成两个子数组,使得每个子数组包含一个只出现一次的数字?

由于异或的结果肯定是那两个只出现一次的数字的异或结果,所以异或结果肯定不为0,也就是说这个结果二进制表示中至少有一位是1。我们可以找到第一个为1的下标位置(记为第n位)作为划分数组的依据。第一个子数组中每个数的第n位为1,第二个子数组的每个数的第n位为0。对于出现两次的数肯定分在同一个子数组中。那两个只出现一次的数字分别分在不同的子数组中。

假设数组为{2,4,3,6,3,2,5,5},异或结果为2,二进制表示为0010。异或得到的结果中倒数第二位为1,于是我们根据倒数第二位是不是为1分为两个子数组。第一个子数组{2,3,6,3,2},其中所有数字的倒数第二位为1;第二个子数组{4,5,5},其中所有数字的倒数第二位为0。接下来只要分别对这两个子数组求异或,就能找出第一个子数组中只出现一次的数字为6,第二个子数组中只出现一次的数字为4。

代码

/*---------------------------------------
*   日期:2015-04-26
*   作者:SJF0115
*   题目: 40.数组中只出现一次的数字
*   网址:http://www.nowcoder.com/books/coding-interviews/e02fdb54d7524710a7d664d082bb7811
*   结果:AC
*   来源:剑指Offer
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int size = data.size();
        if(size <= 1){
            return;
        }//if
        int result = data[0];
        // 所有数XOR
        for(int i = 1;i < size;++i){
            result ^= data[i];
        }//for
        // 二进制中第一个为1的下标
        int index = 0;
        while((result != 0) && ((result & 1) == 0)){
            result >>= 1;
            ++index;
        }//while
        result = (1 << index);
        *num1 = 0;
        *num2 = 0;
        for(int i = 0;i < size;++i){
            // 第index位为1
            if((data[i] & result) > 0){
                *num1 ^= data[i];
            }//
            else{
                *num2 ^= data[i];
            }//else
        }//for
    }
};

int main(){
    vector<int> num = {3,1,10,1,3,6,2,6};
    int* num1 = new int(0);
    int* num2 = new int(0);
    Solution s;
    s.FindNumsAppearOnce(num,num1,num2);
    cout<<*num1<<" "<<*num2<<endl;
    return 0;
}
上一篇:Solaris中获取硬件以及系统配置信息


下一篇:apiCloud中aui获取不到高度,pos.h为0,offsetHeight为0问题