题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
思路
学习了力扣上一个大佬的算法：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/
摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为O(N) 和 O(1) ；
推论一： 若记 众数 的票数为 +1，非众数 的票数为 -1，则一定有所有数字的 票数和 > 0 。
推论二： 若数组的前 a 个数字的 票数和 = 0 ，则 数组剩余 (n-a)个数字的 票数和一定仍 >0 ，即后 (n-a)个数字的 众数仍为 x 。
直接看代码，会更容易理解
public int majorityElement(int[] nums) {
/**
* 找众数
* 定义count为众数出现的次数
* 思路：遍历数组，当count = 0的时候，假设当前遍历到的数字为临时众数，并且 count++；
* count不是0的时候，就判断当前遍历到的数字是否等于临时众数，等于count++，否则count--
*/
int count = 0; //临时众数出现的次数
int x = 0; //临时众数
for (int i = 0; i < nums.length; i++) {
if (count == 0){
x = nums[i];
count ++;
}else {
if (nums[i] == x) count++;
else count--;
}
}
return x;
}
