I think in worst case, @Aeonaxx 's solution is O(n), and @xsh6528 's solution is O(n + (n - m^2 + m) * log(m) ), where m <= sqrt(n), because if you used m buckets, there are 1+2+...m = m*(m+1) numbers.

However, unordered_map's O(n) also has a constant that should not be totally ignored, insertion of hash table is O(1) but it still has a big constant.

So, I think two solutions just have slightly speed difference, because unordered_map take major time.

BY THE WAY, there is a very small mistake in @Aeonaxx 's solution:

for (int i = buckets.size() - 1; i >= 0 && ans.size() < k; --i) {
for (int num : buckets[i]) {
ans.push_back(num);
if (ans.size() == k)
break;
}
}

When it 'break;', it just break the second for(num) loop, but the first for(i) loop continue. So it's still possible that ans.size() > k.