[sword finger offer] 56 - I. the number of numbers in the array

The finger of the sword Offer 56 - I. The number of occurrences of numbers in an array

subject

An integer array nums Except for two numbers , The other numbers appear twice . Please write a program to find out these two numbers that only appear once . The required time complexity is O(n), The space complexity is O(1).

Ideas

  An array nums Do it once or calculate , Get two or operation results that only appear once , Initialize a number m = 1,x and y Is different , So there must be one 1, Then just find it as 1 Binary bit of , It can be nums Split into two sub arrays , Initialize an auxiliary variable m=1 , Judge from right to left through the and operation , Get integer x⊕y Who is it 1. And then split nums For two subarrays , Traverse two sub arrays to execute or , You can get two numbers that only appear once .

Code

class Solution {
    
public:
    vector<int> singleNumbers(vector<int>& nums) {
    
        int x = 0, y = 0, n = 0, m = 1;

        for(int num : nums)         
            n ^= num;

        while((n & m) == 0)       
            m <<= 1;

        for(int num : nums) {
           
            if(num & m) x ^= num;   

            else y ^= num;         
        }

        return vector<int> {
    x, y};  
    }
};