Блог пользователя m.khooryani

TLE in sorting problem
Автор m.khooryani, история, 9 лет назад, По-английски

why I got Time Limit in this problem?

solution

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thank you!

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

    but what's the difference?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

      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))

      → Ответить