摩尔投票法
最近在刷 LeetCode 遇到一个咋想也不会的问题：
在长度为
n的数组中找出重复次数超过n/2的数，要求时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。
摩尔投票法就是满足这些复杂度条件的算法。
摩尔投票法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。
Notice
摩尔投票法是一开始就假定数组中有众数，如果数组中没有众数，那么结果很可能是错误的。需要进行额外判断。
摩尔投票法的具体实现思路是这样的：
使用两个变量来表示当前的众数和它出现的次数，遍历数组：
- 若
count为0，则把当前数组元素赋给num，并且count自增。 - 如果
count不为0，如果当前元素和num不相等，count递减。如果相等就递增。
说白了这就是个对拼消耗，是众数的元素看成一个帮派，不是众数的看成另一个帮派，两个帮派对拼，每次都是单挑。在保证 1v1 肯定同归于尽的条件下，肯定是众数人多的这一边赢。
/**
* @param {number[]} nums
* @return {number}
*/
function majorityElement(numArr) {
let num,
count = 0
for (let i = 0; i < numArr.length; i++) {
if (count === 0) {
num = numArr[i]
count = 1
} else if (num === numArr[i]) {
++count
} else {
--count
}
}
// 进行判断，验证最后剩下的数出现次数是不是真的超过数组的一半
count = 0
for (let i = 0; i < numArr.length; i++) {
if (numArr[i] === num) ++count
}
return count > parseInt(numArr.length / 2) ? num : -1
}