遇到一个很有意思的题目，学到了一个新的算法【摩尔投票法】，记录一下~
题目是这样的：
- 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例：
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
本来我的想法是对数组进行排序，中间的那位数字一定是要找的元素，但是提交后发现占用的时间和内存都非常大，发现别人使用的都是【摩尔投票法】，且时间复杂度为O(n)，空间复杂度为O(1)。
摩尔投票法的思路是这样的：
利用抵消原理，如果一个元素的占比超过一半，那它出现的次数就可以抵消掉其他元素出现次数。
先将第一个数记录为临时答案，记录为res，此时这个答案出现的次数为1，记录为count。然后从第一位开始，循环数组，如果在循环中遇到和res值相等的元素，出现次数加一，count++；如果当前循环到的元素和res不相等，抵消一次，count--；当count为0时，前面的元素已经全部抵消，将res修改为全部抵消后的第一个元素，count重新变为1。重复这个过程，直到结束循环，此时留下来的res，就是出现次数最多的那个元素。
代码实现：
function majorityElement(nums: number[]): number {
let res = nums[0];
let count = 1;
for (let i = 1; i < nums.length; i++) {
if (res == nums[i]) {
count++;
} else {
count--;
}
if (count == 0) {
res = nums[i];
count = 1;
}
}
return res;
}
