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 < 90 less or equals elem[90]

  1. How can I calculate occurences?
  2. Imagine, that we calculated occurences and it is less than 10. What would be the next step?



  • $\begingroup$ The hint seems wrong. Can you double check? $\endgroup$ – Apass.Jack Dec 2 '18 at 14:31
  • $\begingroup$ @Apass.Jack, dl4.joxi.net/drive/2018/12/02/0005/3037/338909/09/… $\endgroup$ – gstackoverflow Dec 2 '18 at 14:34
  • $\begingroup$ Finally I can see the hint make sense! $\endgroup$ – Apass.Jack Dec 3 '18 at 16:26
  • $\begingroup$ @Apass.Jack, could you elaborate? $\endgroup$ – gstackoverflow Dec 3 '18 at 16:50
  • $\begingroup$ Yes, I will. The basic idea is divide and conquer built on top of quickselect. $\endgroup$ – Apass.Jack Dec 3 '18 at 16:54

Your question has been answered in this nice explanation on the classic Misra-Gries summary.

The extra twist here is that you are giving the following misleading or, frankly, wrong hint.

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

I do not believe quickselect can be helpful here. I do not believe it is very helpful if you have obtained the (n/10)-th largest key. Largeness has nothing to do with number of occurrences. That hint looks like a result of momentarily glitch of its author, if it is not an intentional hoax.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.