260 - Single Number III

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, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Hide Tags

Bit Manipulation

Hide Similar Problems

(M) Single Number (M) Single Number II

延续之前的思路，继续异或，全部数组异或出来的结果，应该就是两个单独出现的数字的异或结果。
既然是异或的结果，就说明，结果中某个为 1 的 bit，对应在这两个数字中，该 bit 一定不同。
因此就用这个 bit 当作掩码，来将数组分成两个不同的部分，每个部分各自只包含一个单次出现的数字。
然后就只需要分别异或这两部分，异或的结果，就是所要寻找的两个数字了。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sz=nums.size();

        int tmp=0;       
        for(int ii=0; ii<sz; ++ii)
            tmp ^= nums[ii];

        int mask=1;
        while(0==(tmp&(mask)))
            mask<<=1;

        int rst1=0, rst2=0;
        for(int ii=0; ii<sz; ++ii)
            (0==(mask&nums[ii]))?(rst1^=nums[ii]):(rst2^=nums[ii]);

        vector<int> rst(2, 0);
        rst[0]=rst1, rst[1]=rst2;
        return rst;
    }
};
16 ms