Share my c++ solutions using bit manipulation and sort with explanations.


  • 14
    Y
    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            // solution1:using sort
            // vector<int> res;      
            // sort(nums.begin(),nums.end());
            // if(nums.size() == 2 && nums[0] != nums[1]) return nums;
            // for(int i = 0; i < nums.size();) {
            //     if((nums[i] != nums[i + 1])) {
            //         res.push_back(nums[i]);
            //         i ++;
            //     }
            //     else  i = i + 2;
            // }
            // return res;
            //solution2:using bit manipulation
            int n = 0;  
            vector<int> res;
            for(int i = 0; i < nums.size(); i++) {
                n = n ^ nums[i]; 
            }
           /*flag is the last "1" bit of n,the two elements which appear only once must be defferent in this bit
           so we can use flag to devide all the elements into two parts,one contains a and the other one contains b.*/
            int flag = n & (~(n - 1));
            int a = 0,b = 0;
            for(int i = 0; i < nums.size(); i ++) {
                if((flag&nums[i]) == 0) a ^= nums[i];
                else b ^= nums[i];
            }
            res.push_back(a);
            res.push_back(b);
            return res;
        }
    };

  • 1
    S

    I implemented the same idea, but I don't know: what mean the sign '~'.
    As I understand it means all bits turned, isn't it?

    class Solution {
    public:
        vector<int> singleNumber(vector<int>& nums) {
            int pre = 0;
            for (auto& num : nums) {
                pre ^= num;
            }
            
            int div = 1;
            while ((div & pre) == 0) { div = div << 1; }
    
            vector<int> answ(2);
            for (auto& num : nums) {
                (num & div) ? (answ[0] ^= num) : (answ[1] ^= num);
            }
            return answ;
        }
    };

  • 0
    Y

    Yes.'~' means all bits turned in (n - 1). This was all done to find the different position between a and b. I think your answer is better than mine.


  • 0
    Y

    n & (~(n - 1)) and div in your answer are equivalent.


Log in to reply
 

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