C++ O(n) complex solution easy to understand


  • 4
    Y
    class Solution{
    public:
    	int singleNumber(int A[], int n){
    		int oneNum = 0;
    		int twoNum = 0;
    		int threeNum = 0;
    		for(int i = 0 ; i < n ;i++){
    			threeNum = twoNum & A[i];
    			twoNum = oneNum & A[i] | twoNum;
    			oneNum = oneNum | A[i];
    			oneNum = oneNum &(~threeNum);
    			twoNum = twoNum & (~threeNum);
    			threeNum = 0;
     		}
    		return oneNum;
    	}
    };
    

    easy to understand this solution

    ----------
    
    
    oneNum means A[i] contains one bit 1
    towNum means A[i] contains two bit 1
    threeNum means A[i] contains three bit 1
    if three bit 1 occurs than flip oneNum to 0 and twoNum to 0 and threeNum to 0
    so the step will be like this
    bit in oneNum will change  like this 0-1-1-0
    bit in twoNum will change like this 0-0-1-0
    bit int threeNum will change like this 0 -1-0
    
    and it is easy to expand to other situations like four same num and so on

Log in to reply
 

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