260. Single Number III

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unsigned int diff = 0;
        for(int n:nums) diff^=n;
        diff &= (-diff);
        int a=0, b=0;
        for(int n:nums){
            if(n&diff) a^= n;
            else b^=n;
        }
        return {a,b};
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)