[leetcode] 260. Single Number III

Given an array of numbers nums,in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1,2,1,3,5],return [3,5].

Answer:
假设要找的两个数为a，b。将数组中所有数异或得到a^b。因为a和b不同，所以a^b至少有一位为1。
假设第K位为1，构造一个第k位为1其他位为0的数和数组中所有数求与，来判断某数k位是否为1。
将k位为1的所有数进行异或，则得到a和b中的一个。另一个就简单了。

Code:

 singleNumber(vector& nums) {
        int ab = 0,a = 0,b = 0;
        for(auto i:nums){
            ab ^= i;
        }
        int check = ab & ~(ab-1);
        for(auto i:nums){
            if(i&check){
                a ^= i;
            }
        }
        b = ab ^ a;
        vector res;
        res.push_back(a);
        res.push_back(b);
        return res;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!