Please tell me why TLE here? thanks.


  • 0
    Q

    I used liner search with 2 pointers. But i got the TLE.

    public int singleNumber(int[] A) {
            int m = 0;
            int n = 1;
            if(A.length == 1) {
                return A[0];
            }
            while(A[m] != A[n] ) {
                n++;
                if(n==A.length) {
                    return A[m];
                }
                if(A[m] ==A[n]){
                    m++;
                    n = m+1;
                } 
                
            }
            return 0;
        }

  • 2
    M

    The algorithm you are using runs in O(n^2) time, not linear, since n can basically reach the halfway point each time before being called back, taking O(n/2)=O(n) time per check for each of n checks at worst. You can see this occur in the array:

    [1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,10]
    

    Starting with A[0]=1, the algorithm traverses 9 elements, or half the array, before finding the double. m then advances to the 2, and traverses 9 elements again, taking n/2 time, or n total. Repeat until the first double, and you get n/2*n/2. Even just this is O(n^2) time, and you still need to check that there are no more repeating numbers (there aren't) and find the singleton (your algorithm fails here, returning the second 1).

    The reason you get a TLE instead of a "wrong answer" is because the correct algorithm can solve this puzzle in O(n) time.

    Solution follows:


    int x=0;
    for(int i:A) x^=i;
    return x;

Log in to reply
 

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