My linear complexity without using extra memory solution


  • 8
    C

    Hi all,

    I have a different solution here which take no extra memory. This algorithm is based on the three way partition method. First, choose a element in the array as pivot. Second, split this array to three partition, less than pivot, equal to pivot and greater than pivot. Now we have three partitions and we also know the size of these three partitions too. If the single number in any partition, the size of this partition must be 2*n+1, and should not be divisible by 2. Last, we just recursively find the single number in the partition which size can not be divisible by 2.

    This method can be easily modified to solve the single number 2 problem.

    void swap(int A[], int a, int b)
    {
        int t = A[a];
        A[a] = A[b];
        A[b] = t;
    }
    
    void threeWayPartition(int A[], int n, int&l, int&h)
    {
        int pivot = A[0];
        int j = -1;
        int k = n;
        
        for (int i=0; i<k;)
        {
            if (A[i] < pivot)
            {
                swap(A, i, ++j);
                i++;
            }
            else if (A[i] > pivot)
            {
                swap(A, i, --k);
            }
            else
            {
                i++;
            }
        }
        
        l = j;
        h = k;
    }
    
    #define APPEAR_NUMBER (2)
    
    class Solution {
    public:
        int singleNumber(int A[], int n) {
            if (n==1)
            {
                return A[0];
            }
    
            int l=0;
            int h=0;
            threeWayPartition(A, n, l, h);
            
            int p = l+1;
    
            if (A[p] != A[p+1])
            {
                return A[p];
            }
            else if(p%APPEAR_NUMBER == 0)
            {
                return singleNumber(A+(p+APPEAR_NUMBER), n-(p+APPEAR_NUMBER));
            }
            else
            {
                return singleNumber(A, p);
            }
        }
    };

  • 0
    S

    Nice thought. Although strictly speaking, any non-trivial recursive algorithm uses extra stack memory, and so does yours. If you can rewrite your algorithm in an iterative way, then the necessity of extra memory may be removed.


  • 0
    C

    Yes, as stellari said, my non-trivial recursive algorithm did use extra stack memory. So I rewrite my algorithm in an iterative way. Here is my revised algorithm. Please help to check.

    void swap(int A[], int a, int b)
    {
        int t = A[a];
        A[a] = A[b];
        A[b] = t;
    }
    
    void threeWayPartition(int A[], int n, int&l, int&h)
    {
        int pivot = A[0];
        int j = -1;
        int k = n;
        
        for (int i=0; i<k;)
        {
            if (A[i] < pivot)
            {
                swap(A, i, ++j);
                i++;
            }
            else if (A[i] > pivot)
                swap(A, i, --k);
            else
                i++;
        }
        
        l = j;
        h = k;
    }
    
    #define APPEAR_NUMBER (2)
    
    class Solution {
    public:
        int singleNumber(int A[], int n) {
            if (n == 1)
                return A[0];
    
            int l = 0;
            int h = 0;
            int p = 0;
            
            while (1)
            {
                l = 0; h = 0;
                threeWayPartition(A, n, l, h);
                
                p = l+1;
        
                if (A[p] != A[p+1])
                    return A[p];
                else if(p % APPEAR_NUMBER == 0)
                {
                    A += (p + APPEAR_NUMBER);
                    n -= (p + APPEAR_NUMBER);
                }
                else
                    n = p;
            }
        }
    };

  • 0
    E

    But I think the average complexity is O(nlogn), and the worse is O(n²), just as qsort


  • 0
    G

    It's similar to quick sort, but the key difference is that you don't have to revisit the intervals where it is certain that the target is not in. So on average the complexity is O(n). And yes, I think the worst case is O(n^2).


  • 0
    C

    As GuaGua's comment, we only need to revisit the partition with 2*n+1 size. The average complexity should be n + n/2 + n/4 + .... = O(n), and yes the worst case is O(n^2) without pivot selection enhancement.


Log in to reply
 

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