m.khooryani's blog

TLE in sorting problem
By m.khooryani, history, 11 years ago, In English

why I got Time Limit in this problem?

solution

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Probably anti-quicksort test? Arrays.sort for primitive types is O(n2) in worst case. Use Long instead of long or shuffle before sorting.

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

    thank you!

    got AC by using Integer[] instead of int[]

    but what's the difference?

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
      ← Rev. 4  
      Vote: I like it +1 Vote: I do not like it

      For primitives types java uses "dual pivot" Quick Sort (please google it, it's something like modernized Quick Sort), and for object java uses Tim Sort.

      Take a look at Collections.sort which use Merge Sort (O(nlogn))

      → Reply