Checking whether at least n/2 + 1 elements of a set/vector are equal - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:48:12Z https://cs.stackexchange.com/feeds/question/82002 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/82002 0 Checking whether at least n/2 + 1 elements of a set/vector are equal Jose https://cs.stackexchange.com/users/78116 2017-10-03T11:05:54Z 2017-10-04T16:10:26Z <p>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. </p> <p>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.</p> <p>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.</p> <p>Could you give me some advice? Thank you very much. </p> https://cs.stackexchange.com/questions/82002/checking-whether-at-least-n-2-1-elements-of-a-set-vector-are-equal/82011#82011 1 Answer by Simon for Checking whether at least n/2 + 1 elements of a set/vector are equal Simon https://cs.stackexchange.com/users/68194 2017-10-03T14:34:05Z 2017-10-03T19:09:08Z <p>I think there is an even better approach to your problem: </p> <ol> <li>The element you are looking for will also be the median of the list. Find the median of the list using the <a href="https://en.wikipedia.org/wiki/Median_of_medians" rel="nofollow noreferrer">Median of Medians</a> algorithm. <strong>\$O(n)\$ complexity</strong></li> <li>Check if the median appears at least \$n/2 + 1\$ times on the list <strong>\$O(n)\$ complexity</strong></li> </ol> <p>So, the algorithm you're looking for runs in linear time. </p>