258. The Majority Element

Print the value that appears MORE than n/2 times among n integers, or -1 if no value does.

Strictly more than half. In 1 1 2 2 neither value qualifies, because two is not more than two.

Sorting gives a neat solution: if a majority exists it must occupy the middle position, so check whether the value there actually appears often enough. That is O(n log n).

There is also a beautiful O(n) solution using no extra memory. Pair off values that differ, and anything left standing at the end is the only possible majority. It still needs verifying, which is why the last step is a count.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 1000000000`