Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times.

You may assume that the array is non-empty and the majority element always exist in the array.

This problem is super easy, my first thinking is to sort the array and pick the middle element.

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

But what if I can’t sort the array so easily?

Then we can use “Boyer–Moore majority vote algorithm”, which is a linear-time majority vote algorithm.

Initialize an element m and a counter i with i = 0
For each element x of the input sequence:
If i = 0, then assign m = x and i = 1
else if m = x, then assign i = i + 1
else assign i = i − 1
Return m

Here’s a good graph illustration of how Moore Voting algorithm works by its inventor Moore

Solution for this problem:

// Moore voting algorithm
public int majorityElement3(int[] nums) {
    int count=0, rets = 0;
    for (int num: nums) {
        if (count==0)
            res = num;
        if (num!=ret)
            count--;
        else
            count++;
    }
    return res;
}