Linear complexity but still exceeding the time limit


  • 0
    B

    Here's my code. It's not efficient and a kind of stupid but I think its run time complexity is O(n). I don't know why it still exceeds the time limit...

    int count[65536];
    int single = 0;
    int i = 0;
    
    for (i = 0; i < n; i ++)
    {
        count[A[i] % n] = 0;
    }
    
    for (i = 0; i < n; i ++)
    {
        count[A[i] % n] += 1;
    }
    
    for (i = 0; i < n; i ++)
    {
        if (count[A[i] % n] == 1)
        {
            single = A[i];
            break;
        }
    }
    
    
    return single;
    }

  • 0
    S

    What if A[i] is negtive?

    What's the meaning of % n? If A[i] = MAX_INT, n = 1, index is out of range.

    I think your method is inappropriate for this problem.


  • 0
    I

    try {0,3,3}, it is not just time issue. xor all element you will get the answer.


  • 1
    S

    It is not correct actually. So it makes no sense to reason about the complexity. You could have a hash collision.

    What if
    A = {0,0,3}, n = 3


Log in to reply
 

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