Data Structures, Algorithms, & Applications in C++
Chapter 14, Exercise 23
Suppose we have the 12 elements [6, 7, 2, 5, 6, 2, 5, 7, 6, 2, 5, 5].
The distinct elements and their frequencies can be determined
by first sorting the elements to get the array
[2, 2, 2, 5, 5, 5, 5, 6, 6, 6, 7, 7]. The number of 2s can be determined
by scanning the sorted elements from left to right looking for the
first element that is not 2. This element, 5, is in position 3. So there
are three 2s. To determine the number of 5s, we scan rightwards from
the location c = 3 of the first 5 to the
location j = 7 of the first element that is not a 5.
The number of 5s is j - c = 4.