trek
June 5, 2014, 1:37pm
1
In JAVA is there any difference in using Integer and int at run time ??
1.Integer n[] = new Integer[100000];
2.int n[]= new int[1000000];
on solving this question i got AC when i used Integer ,but got TLE when i used int .My code for that problem is Iqq22S - Online Java Compiler & Debugging Tool - Ideone.com
plzz explain the difference of using them and why much time is taking while using primitive data type int .
This might be useful to you to read:
Best,
Bruno
1 Like
Really?
As I can see, there is a note:
Please be careful that answer might not fit in 32 bit data type.
Typically using Integer is slower comparing to int as far as I know. Please post submission links.
1 Like
When you use integer merge sort is used, while using int quick sort is used so an anti-quick sort input would lead to TLE.
1 Like
I see now, the reason is in Arrays.sort(c);
- when primitive types are used, quicksort is used, when Objects (like Integer) merge sort is used.
Codeforces, unfortunatelly, has anti quicksort inputs, I really hate this… If you want try to shuffle before sorting and you will see, but there is not easy (one liner) way how to do that in Java
If you decide to do so, look at Fisher–Yates shuffle (this was in Google Code Jam 2014 also - here ).
1 Like
@u_seem_surprsd is correct merge sort instead of heap sort - fixed
trek
June 5, 2014, 10:40pm
8
ok !! merge sort takes o(n*log n) for worst case but quicksort takes o(n^2) for worst case…
thnxxx