0
$\begingroup$

We have a set of elements, say a vector of $n$ elements (actually, the data structure really doesn't matter in this case). It is NOT sorted. We want to check whether at least $n/2 + 1$ elements are equal.

I have been thinking about an efficient algorithm to do so but I don't know, the fact that it is not sorted makes it quite difficult for me.

If it was sorted, we could do it with an $O(n)$ algorithm, I'd say: just iterate over the vector, saving the most common element. If the counter arrives to $n/2 + 1$, we are done.

Could you give me some advice? Thank you very much.

$\endgroup$
  • 2
    $\begingroup$ This is a standard exercise -- I suggest you think about it some more, especially in the context of the course in which it was set. $\endgroup$ – David Richerby Oct 3 '17 at 11:11
  • $\begingroup$ Thanks for your answer. Could you give me a hint, at least? What about Hoare's selection to find the median (O(log(n)), and then checking how many times does this element appear? This would be O(log(n) + n), but I'm being asked to find a O(nlog(n)). $\endgroup$ – Jose Oct 3 '17 at 11:19
  • $\begingroup$ An algorithm which runs in time $O(\log n + n)$ also runs in time $O(n\log n)$. $\endgroup$ – Yuval Filmus Oct 3 '17 at 13:56
  • $\begingroup$ @Jose If all you want is an $O(n\log n)$ algorithm, just sort the list. Hoare's selection algorithm requires at least linear time (you can't possibly find the $k$th-largest element of a list without looking at every element) and may take quadratic time in the worst case. $\endgroup$ – David Richerby Oct 3 '17 at 15:13
  • $\begingroup$ (Not knowing what David Richerby is thinking of,) First hint: $O(n)$ does not mean/imply single pass. (Errm - $O(nlogn)$? Well, sure includes $O(n)$.) $\endgroup$ – greybeard Oct 3 '17 at 19:31
1
$\begingroup$

I think there is an even better approach to your problem:

  1. The element you are looking for will also be the median of the list. Find the median of the list using the Median of Medians algorithm. $O(n)$ complexity
  2. Check if the median appears at least $n/2 + 1$ times on the list $O(n)$ complexity

So, the algorithm you're looking for runs in linear time.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure the condition $count=n/2+1$ is correct. If the array consists of $n/2+1$ copies of $x$ followed by $n/2-1$ copies of $y$, you will get 2 at the end. $\endgroup$ – Yuval Filmus Oct 3 '17 at 18:48
  • $\begingroup$ @YuvalFilmus Thanks, I misinterpreted the problem. Now I updated the solution, feel free to check it :) $\endgroup$ – Simon Oct 3 '17 at 19:10

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.