遇到一个很有意思的题目，学到了一个新的算法【摩尔投票法】，记录一下~
题目是这样的：

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

输入: [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;
}