public class Solution {
public int majorityElement(int[] num) {
int ele = num[0];
int counter = 0;
for(int n : num) {
if(n == ele) {
counter++;
}
else {
counter;
}
if(counter == 0) {
ele = n;
counter = 1;
}
}
return ele;
}
}
Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.
My java solution


Proof by contradiction:
Let M be the majority element, and let there be k of M in the array.
Suppose the above algorithm did not return M. Then the k M's are canceled by k numbers different from M.
Thus the array has at least 2k numbers.
Since M is the majority element, k > n/2, and therefore 2k>n. This indicates that the array has more than n numbers, a contradiction.