Блог пользователя vivekiitian

Changing "int" to "Integer" gives significant performance improvement!
Автор vivekiitian, история, 5 лет назад, По-английски

I tried to solve this problem. Refer to my solution 1 and 2. The only difference between those solutions is datatype int is replaced by Integer and solution got accepted (runtime got reduced from more than 1s to 140 ms). Any idea why is it happening?

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

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

Arrays.sort use Quick Sort (Worst case complexity of O(n^2)) when passing an array of primitive values, and Merge Sort (Worst case complexity of O(n log(n))) when using an array of object references.

I assume the problem has got some anti-tests against inefficient sorting.

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

Java sorts primitive types by quick sort which is O(N^2) in the worst case, while it sorts Objects in O(nlogn) using merge sort I think.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Learn to read the API documentation (for your own good).

→ Ответить