问题描述

小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. 投票阶段：首先选择一个候选数字，并将它的票数初始化为 1。然后遍历数组中的每个数字：

   • 如果当前数字和候选数字相同，票数加 1。
   • 如果当前数字和候选数字不同，票数减 1。如果票数减为 0，则选取当前数字作为新的候选数字，并将票数重置为 1。

2. 确认阶段：在摩尔投票阶段结束后，我们得到一个候选数字。由于题目保证有一个数字出现次数超过数组总数的一半，因此最后的候选数字就是我们要找的数字。

代码实现:

代码解释

1. 摩尔投票算法：

   • 我们使用 candidate 来记录当前的候选数字，count 来记录候选数字的票数。
   • 如果票数为零，说明之前的候选数字被“淘汰”了，我们就将当前数字设为新的候选数字，并将票数设为 1。
   • 如果当前数字与候选数字相同，票数加 1。
   • 如果当前数字与候选数字不同，票数减 1。

2. 保证正确性：

   • 根据题目描述，存在一个数字的出现次数超过数组总长度的一半，因此最终的 candidate 一定是正确的数字。

时间复杂度

• 时间复杂度：O(N)，其中 N 是数组的长度。我们只需要遍历数组一次来找到候选数字。
• 空间复杂度：O(1)，只用了常数空间。

测试用例

1. 输入：[1, 3, 8, 2, 3, 1, 3, 3, 3]

   • 输出：3，3 出现了 5 次，超过了一半。

2. 输入：[5, 5, 5, 1, 2, 5, 5]

   • 输出：5，5 出现了 5 次，超过了一半。

3. 输入：[9, 9, 9, 9, 8, 9, 8, 8]

   • 输出：9，9 出现了 5 次，超过了一半。