169. Majority Element

https://leetcode.com/problems/majority-element/

use

Boyer-Moore Majority Vote Algorithm

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html

/*
    time complexity: O(n), space complexity: O(1)
*/
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int majority = 0;
        
        for (int num : nums) {
            if (count == 0) {
                majority = num;
                count++;
            } else if (num != majority) {
                count--;
            } else {
                count++;
            }
        }
        return majority;
    }
}