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).
You can use radix sort which is linear for fixed width ints.
Although 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).
Even 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)