169. Majority Element

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.

related question: Majority Element II

brute force solution is to count. one O(n) solution is to keep track of the major number from the beginning, in this way the major number may vary during the process, but at the end, only the real major number will remain. for each pair of number, if they are same increase count of major number, if not, this pair will be removed.

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int major = 0;
        for(int val : nums){
            if(count == 0){
                major = val;
                count =1;
                continue;
            }
            if(major == val) count++;
            else count--;
        }
        return major;

    }
}