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

数组中只出现一次的数字

http://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size()<2)return;
        int resultExclusiveOr = 0;
        for(int i = 0; i < data.size();i++){
        resultExclusiveOr ^= data[i];
        }
        int indexof = FindFirstBitIs(resultExclusiveOr);
        *num1 = *num2 = 0;
        for(int j = 0 ;j < data.size();j++){
            if(isBit(data[j],indexof)){
                *num1 ^= data[j];
            }else{
                *num2 ^= data[j];
            }
        }
    }
    int FindFirstBitIs(int num){
        int indexBit = 0;
        while(((num & 1) ==0 )&& (indexBit < (8 * sizeof(int)))){
            num >>= 1;
            indexBit++;//to Mark the number of the place where an exception has started
        }
        return indexBit;// to return the place
    }
    bool isBit(int num,int indexBit){
        num>>=indexBit;//to judge the mark place inoder to separate the numbers
        return num & 1;
    }
};
这道题中,*num1 和 *num2是返回的两个值。
在这个数组中有两个数是只出现一次。
将这个数组中的数进行全部的异或。因为相同的数字异或等于0,任何数字和0进行异或还等它本身。
这个数组中的所有的数字进行异或之后,得到的值就是那两个不相同的数字异或的结果,因为相同的数字异或都进行抵消了。
对得到的结果进行判断其二进制从第几位开始是1,依据这一位,将这两个数字进行划分到不同的两类中,然后进而也可以将数组中的全部数字都按照这个分类法则进行分类。
数组中的数按照这个分类法则将数字分为了两类,将每一类中的数字进行全部的异或,得到的结果就是其中的一个数字。共两类,就得到了两个数字的结果。
全部评论

相关推荐

卓望数码 Java开发岗 总包23+1~2福利补贴,公积金12%
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务