Count frequencies with a hash map, then sort all unique elements by their counts. Take the first k.
With nums = [1, 1, 1, 2, 2, 3] and k = 2, you get counts {1: 3, 2: 2, 3: 1}. Sort by value descending: [(1, 3), (2, 2), (3, 1)]. Take top : [1, 2].
Sorting is where is the number of unique elements. In the worst case, , so this becomes .
Can you do better than ?