j1gsaw's blog

Having problem with 433B question
By j1gsaw, 10 years ago, In English

I don't understand why my code is giving TLE for this question when my complexity is O(nlogn).. Please somebody look at my code and find the bug.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It's possible you ran into an "anti-quicksort" test, since Arrays.sort on primitive types in Java 7 has worst case O(n^2) and on others is an O(n log n) mergesort. Unfair I know, but I don't see anything else that could justify so many people failing on test 46.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanx bli0042 . Do you know how to overcome with this problem?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can use mergesort How to write it

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      You don't need to write your own mergesort, but if you change "int" to "Integer" it's not a primitive type anymore so Arrays.sort will do a mergesort instead. :)

      → Reply