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$
6
  • 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$ Commented Oct 3, 2017 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$
    – nohamk
    Commented Oct 3, 2017 at 11:19
  • $\begingroup$ An algorithm which runs in time $O(\log n + n)$ also runs in time $O(n\log n)$. $\endgroup$ Commented Oct 3, 2017 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$ Commented Oct 3, 2017 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
    Commented Oct 3, 2017 at 19:31

1 Answer 1

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$
2
  • 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$ Commented Oct 3, 2017 at 18:48
  • $\begingroup$ @YuvalFilmus Thanks, I misinterpreted the problem. Now I updated the solution, feel free to check it :) $\endgroup$
    – Simon
    Commented Oct 3, 2017 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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