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.