Majority Number

Given an array of integers, the majority number is
the number that occurs more than half of the size of the array. Find it.

Example
Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge
O(n) time and O(1) extra space

解题思路： 既然某个数超过二分之一，那么用这个数和其他数进行 PK， 不同的计数器都减一（核心在于两两抵消）， 相同的则加1，最后返回计数器大于0的即可。

Java代码：

public int majorityNumber(ArrayList<Integer> nums) {
    if (nums == null || nums.isEmpty()) return -1;

    // pair<key, count>
    int key = -1, count = 0;
    for (int num : nums) {
        // re-initialize
        if (count == 0) {
            key = num;
            count = 1;
            continue;
        }

        // increment/decrement count
        if (key == num) {
            count++;
        } else {
            count--;
        }
    }

    return key;
}