A general solution to find single number including 2, 3, 5, 7 and so on....


  • 1
    C

    My approach is using the idea of the quest sort method:

    1. Partition A[] into two sub array, all items in left array <= key, all items in right array > key;

    2. if left array length modulo 3 not equal 0, then the single number in the left sub array, otherwise the single number in the right sub array.

    3. using the recursion call to get the result.

    For other similar problem, like 4 times, 5 times, 6 times etc. you just need to change the modulo to 4,5,6, etc.

    here is my code for 3 times:

    int findSingle(int A[], int b,int e)
    {
        if(e-b<3)
            return A[b];
        
        int i=b,j=b+1,key= A[b],temp;
        int m=b;
        while(A[b]==A[e-1]) // Adjust special case
        {
            m++;
            temp= A[m];
            A[m]= A[b];
            A[b]= temp;
            key= temp;
        }
        
        // Partition 
        for(; j<e; j++)
        {
            if(A[j] <= key)
            {
                i++;
                temp= A[j];
                A[j]= A[i];
                A[i]= temp;
            }
        }
        A[b]= A[i];
        A[i]= key;
        
        // recursion 
        if((i-b+1)%3)
            return findSingle(A,b,i+1);
        else
            return findSingle(A,i+1,e);
    }
    
    int singleNumber(int A[], int n) 
    {
        return findSingle(A,0,n);
    }

  • 0
    G

    what about the number appear only once is 3n? 3,6,9.
    This is not a solution.


  • 0
    C

    What you asked is another problem, not the "Single Number" problem. Pls read the problem title carefully.


  • 0
    X

    it's not the right solution, cannot works well for case like 3,2,3,3.


  • 0
    C

    I have tested it, the result is 2. Is their anything wrong?


Log in to reply
 

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