m.khooryani's blog

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

why I got Time Limit in this problem?

solution

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

»
9 years ago, # |
  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
  • »
    »
    9 years ago, # ^ |
      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
    • »
      »
      »
      9 years ago, # ^ |
      ← 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