Why O(n*log(n)) Solution can be accepted ?


  • 0
    class Solution {
    public:
        int singleNumber(int A[], int n) {
            sort(A, A+n);
            for (n = n-1; n >= 2 ; n -= 3)
                if (A[n] != A[n-2])
                    return A[n];
            return A[0];
        }
    };

  • 0
    T

    why not?

    it is also a good solution :)


  • 1
    M

    Because the ideal solution is O(n), this solution would in theory get "Time Limit Exceeded." However, the program for checking solutions does not actually calculate the time complexity of any given solution. It has a set time limit for each given test case, and if the solution for that case exceeds the time limit, it fails.

    The problem arises, however, in deciding the time limit for the test case. You need to make it large enough that the ideal solution, no matter how poorly the compiler runs it, will not exceed the limit, but still be low enough that most (ideally all) solutions with greater time complexity will exceed it. With your solution, your program solves the test cases in under the time limit, so is accepted. If you submit again however, the compiler will recompile it, and may exceed the time limit, failing you then.

    The best solutions are simply those that will never exceed the limit, not just those solutions that get accepted under a favorable compilation.


  • 0

    Thanks bro!!!


  • 0

    I think it should be a liner solution... Thanks any way! :)


Log in to reply
 

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