algorithm to find all values that occur more than n/10 times

I took an algorhytm course on coursera and there some optional questions for student enrichment. I can't solve the following task:


Decimal dominants. Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected
running time of your algorithm should be linear.

And authors provied following hint:


Hint: determine the (n/10)-th largest key using quickselect and check
if it occurs more than n/10 times.

Actually it is not cleat for me how can quick select help me. quick select is algorhitm which can help to find k-th largest element in linear time. In the lecture materials written that it work approximately linear.

Let's work with example. We have 100 elements array. We found 10-th elements.
( frankly speaking according the book we found such element order that all elements with index > 90 more or equals than elems[90] and all elements with index

• Imagine, that we calculated occurences and it is less than 10. What would be the next step?

P.S.

Perhaps the hint was aiming at the following approach. Suppose that the array were sorted. If a value appears $m$ times and we divide the array into intervals of length $m$, then the value must appear at the end of one of the intervals. This suggests the following algorithm for finding all values that appear $n/C$ times: compute the $i \cdot n/C$-largest elements for $1 \leq i \leq C$, and for each of them, check whether the value appears at least $n/C$ times. Each iteration takes $O(n)$ time using Quickselect, for a total of $O(Cn)$ time.

StackExchange Computer Science Q#100876, answer score: 2