Share my bit sort solution. Not as fast as xor solution, but accepted.


  • 0
    F

    The idea is partition sort nums bit by bit. It takes O(32n) then find the singles in another O(n). The recursion takes O(logN) space.

     void sort(vector<int> & nums, int s, int e, int bit) {
            if (s >= e || bit < 0) return;
            int j = s, mask = (1 << bit);
            for (int i = s; i < e; i++) {
                if (!(nums[i] & mask)) swap(nums[j++], nums[i]);
            }
            sort(nums, s, j, bit-1);
            sort(nums, j, e, bit-1);
        }
        vector<int> singleNumber(vector<int>& nums) {
            sort(nums, 0, nums.size(), 31);
            vector<int> res;
            for (int i = 0; i < nums.size()-1 && res.size() < 2;) {
                if (nums[i] != nums[i+1]) {
                    res.push_back(nums[i++]);
                } else {
                    i+=2;
                }
            }
            if (res.size() < 2) res.push_back(nums.back());
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.