2
$\begingroup$

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?

P.S.

http://dl4.joxi.net/drive/2018/12/02/0005/3037/338909/09/d99f2edb52.jpg

$\endgroup$
  • $\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
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.