Finding Frequency of numbers in a given group of numbers

Question

Suppose we have a vector/array in C++ and we wish to count which of these N elements has maximum repetitive occurrences and output the highest count. Which algorithm is best suited for this job.

example:

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

the output is 4 because 2 occurs 4 times. That is the maximum number of times 2 occurs.

Answer 1

Sort the array and then do a quick pass to count each number. The algorithm has O(N*logN) complexity.

Alternatively, create a hash table, using the number as the key. Store in the hashtable a counter for each element you've keyed. You'll be able to count all elements in one pass; however, the complexity of the algorithm now depends on the complexity of your hasing function.

Answer 2

Optimized for space:

Quicksort (for example) then iterate over the items, keeping track of largest count only. At best O(N log N).

Optimized for speed:

Iterate over all elements, keeping track of the separate counts. This algorithm will always be O(n).

Answer 3

If you have the RAM and your values are not too large, use counting sort.