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 and all elements with index < 90 less or equals elem
- How can I calculate occurences?
- Imagine, that we calculated occurences and it is less than 10. What would be the next step?