Lcof 39.数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

​ 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
​ 输出: 2

解法1：哈希表统计法，时间和空间复杂度均为O(N)

解法2：数组排序法，时间复杂度为O(NlongN)

解法3：摩尔投票法，时间复杂度为O(N)，空间复杂度为O(1)

算法原理：

使用 votes 来统计一个元素出现的次数，当遍历到的元素和统计元素相等时，令 votes++，否则令 votes–;

如果前面查找了 i 个元素，且 votes == 0，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，因为如果多于 i / 2 的话 votes 就一定不会为 0；

此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。

class Solution {
    public int majorityElement(int[] nums) {
        int votes = 0, majority = 0;
        for (int num : nums) {
            if (votes == 0) {
                majority = num;
            }
            if (num == majority) {
                votes++;
            } else {
                votes--;
            }
        }
        return majority;
    }
}