找出整型数组中，出现次数超过一半的数

问题描述

小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

测试样例

样例1：

输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出：3

样例2：

输入：array = [5, 5, 5, 1, 2, 5, 5]
输出：5

样例3：

输入：array = [9, 9, 9, 9, 8, 9, 8, 8]
输出：9

实现分析：

1.可以通过哈希表的方式，记录每个数出现的次数，然后找到出现字数超过一半的数。

2.使用摩尔投票法解决

1.哈希表解法

function solution(array: number[]): number {
  let map = new Map<number, number>(); // 存储key为出现的数字,value为出现的次数

  // 遍历，存储
  array.forEach((num) => {
    const count = map.get(num) || 0;
    map.set(num, count + 1);
  });

  // 找出出现次数超过一半的数
  for (const [num, count] of map) {
    if (count >= array.length / 2) return num;
  }
  return -1;
}

function main() {
  // Add your test cases here
  console.log(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) === 3);
}

main();

2.摩尔投票法解法

摩尔投票算法（Boyer–Moore majority vote algorithm）是一种在线性时间内找到数组中出现次数超过一半元素的有效方法。这里，“超过一半”意味着如果数组长度为n，那么这个元素至少出现了(n/2)+1次。我们用一种直观且数学化的方法来解释这个算法。

基本思想

想象一下，你在一个房间里，房间里面的人支持不同的候选人。你的目标是找出那个获得绝对多数票（即超过半数选票）的候选人。但是，你不能直接知道每个人投给了谁，只能通过询问的方式一对一对地比较两个人的选择，并根据结果决定留下谁。如果你发现这两个人支持同一个候选人，则他们都可以留下来；否则，就让他们都离开房间。最后留在房间里的人可能就是得票最多的那位候选人。

算法步骤

初始化：设当前候选人为candidate，计数器count=0。

遍历数组：

对于每个元素x：

如果count==0，则将x设置为新的candidate，并将count设为1。

否则，如果x==candidate，则增加count。

如果x!=candidate，则减少count。

验证：在一轮扫描结束后，candidate可能是但不一定是真正的众数。需要再次遍历数组确认candidate是否真的是众数（即出现次数大于n/2）。

为什么有效？

当两个不同元素相遇时，它们相互抵消了对方的影响（就像两人意见相左而被要求同时离开），这样可以保证即使非众数元素很多，只要众数足够多，它总能在最终保留下来。

如果确实存在一个元素的数量超过了一半，那么按照上述规则操作后，留下的candidate必然是这个元素。

最后的验证步骤是为了确保真的找到了这样的元素。如果没有超过半数的元素存在，那么第二次遍历会揭示这一点。

数学角度的理解

从集合论的角度来看，我们可以把整个过程看作是从原始集合逐步删除成对的不同元素的过程。每次遇到一对不同的元素就将其移除，相当于执行了一个集合运算A｜(B∪C)A ｜ (B∪C)，其中B,CB,C分别代表这两个不同的元素。由于众数定义上数量超过了其他所有元素加起来的数量，因此无论如何配对去除，最终剩下的总是该众数的一部分实例。

总之，摩尔投票算法巧妙地利用了“抵消”的概念，在O(n)时间复杂度下解决了寻找数组中占多数的元素问题，非常适合处理大规模数据集。

function solution(array: number[]): number {
    // Edit your code here
    let num = 0;
    let count = 0;
    array.forEach(item => {
        if (count === 0) {
            num = item;
            count++；
        } else if (item === num) {
            count++；
        } else {
            count--；
        }
    })

    return num;
}

function main() {
    // Add your test cases here
    console.log(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) === 3);
}

main();