Count distinct values first

To find the k most frequent values, first build a frequency map. Let n be the number of input values and u the number of distinct values. Counting takes expected O(n) time and stores u counts.

The selection strategy depends on u, k, the range of possible frequencies, and how much extra memory is acceptable.

Assume 1 <= k <= u, so the requested number of results exists.