Linear time with no extra memory


  • 3
    H

    this is my solution with time O(a*n) where a is the length of the integer. I solve the problem by using a counting sort (O(n)) method at each digit of the numbers (start from the lowest digit and thus the order is stable) and gradually locate the position of the single number cauz the singular number makes the count of 0s (or 1s) an odd number at that digit.

    class Solution {
    public:
        int singleNumber(int A[], int n){
    	//the digits of integers
    	int length=8*sizeof(int);
    	int count0,count1;
    	//lookup range
    	int posp=0,posq=n-1;
    	//for each digit
    	for(int i=0;i<length;i++){
    		if(posp==posq) return A[posp];
    		//counting 0s and 1s
    		count0=0;count1=0;
    		for(int j=posp;j<=posq;j++){
    			if((A[j]&(1<<i))==0)count0++;
    			else count1++;
    		}
    		//swaping integers with 0s to the front(order stable)
    		int pos0=posp,curpos=posp;
    		while(curpos<=posq){
    			if((A[curpos]&(1<<i))==0){
    				int temp=A[pos0];
    				A[pos0]=A[curpos];
    				A[curpos]=temp;
    				pos0++;
    			}
    			curpos++;
    		}
    		//relocate
    		if(!(count0%2))posp+=count0;
    		else posq-=count1;
    	}
    	return A[posp];
    }
    };

  • 18
    C

    why not:

        int singleNumber(int A[], int n) {
        int x = 0;
        for(int i=0; i<n; i++)
            x ^= A[i];
        return x;
    }
    

  • 0
    H

    Thanks, that's a short and smart answer. I thought about finding the position of the number only


  • 0
    K

    Hi, haomaoer.

    Base your idea, I write this code.

    class Solution {
    public:
        int singleNumber(int A[], int n) {
            int ret = 0;
            int count0 = 0;
            int count1 = 0;
            for (int i=0; i < sizeof(int)*8; ++i)
            {
                count0=0;
                count1=0;
                for (int j=0; j < n; ++j)
                {
                    if (A[j]&(1<<i))
                    {
                        ++count1;
                    }
                    else
                    {
                        ++count0;
                    }
                }
                if (count1%2)
                {
                    ret |= 1<<i;
                }
                else
                {
                    // this bit of ret is 0
                }
            }
    
            return ret;
        }
    };

Log in to reply
 

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