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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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