3 ms·
The hashmap solution here is ideally O(n) as you only iterate once (assuming O(1) lookups and inserts in the map). A sort/search method, even using quicksort wo
by colejohnson66 3y ago
The hashmap solution here is ideally O(n) as you only iterate once (assuming O(1) lookups and inserts in the map). A sort/search method, even using quicksort would be O(n*logn).
- tromp 3y agoYou can use radix sort which is linear for fixed width ints.
- jjgreen 3y agoO(n log n + n) = O(n log n)
- tromp 3y agoAlthough hashmaps are O(n) in practice, they can be worse than O(n log n) on some rare inputs that cause lots of hash collisions. Several sorting algorithms such as mergesort and heapsort are guaranteed O(n log n).
- enedil 3y agoEven it it was O(1) not amortized, it's not possible to beat the sorting in actual execution time for reasonable inputs (less than 10B elements probably)
- topposter32 3y agoWhat's log base 2 of a million or a billion?