My 16ms cpp solution


  • 0
    Z

    1, Calculate the XOR value of the whole nums.

    2, Find the first 1(from the right side) of this XOR value

    3, Divide the nums into 2 parts according to whether the index of step 2 is 1.

    4, For each part calculate the XOR value and get the result.

    class Solution {
    public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorResult = 0;
    	for(int i=0;i<nums.size();i++){
    		xorResult ^= nums[i];
    	}
    	int Index1 = FindTheFirst1(xorResult);
    	
    	int num1=0,num2=0;
    	for(int i=0;i<nums.size();i++){
    		if(nums[i] & (1<<Index1))
    			num1 ^= nums[i];
    		else
    			num2 ^= nums[i];
    	}
    	vector<int> result;
    	if(num1!=0||num2!=0){
        	
        	result.push_back(num1);
    	    result.push_back(num2);
    	}
    	return result;
    	
    	
    }
    int FindTheFirst1(int i){
    	if(i==0)
    		return -1;
    	
    	int index=0;
    	while((i & 1)==0){
    		i = (i>>1);
    		index++;
    	}
    	return index;
    }
    };

Log in to reply
 

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