字节青训Marscode——8：找出整形数组中超过一半的数

问题描述

小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：问题定义与分析

题目要求：

从一个整数数组 array 中找出某个出现次数超过数组长度一半的数字，保证这样的数字一定存在。

输入与输出：

• 输入：一个整数数组 array，长度为 n。
• 输出：数组中某个出现次数超过 n / 2 的数字。

限制与边界条件：

1. 数组中保证一定存在满足条件的数字。
2. 数组长度 n 的范围未明确给出，但假设为合理范围（如 1 <= n <= 10^6）。
3. 只需要输出符合条件的任意一个数字，不需要处理无解的情况。

问题性质：

• 根据题意，某个数字的出现次数超过总数的一半，称为 多数元素。
• 这种问题可以通过经典的算法（如摩尔投票法）高效解决，而不需要使用暴力计数法。

---

步骤2：算法设计与分析

方法1：哈希表计数

• 使用哈希表统计每个数字的出现次数。
• 遍历数组，当某个数字的出现次数超过 n / 2 时返回该数字。

时间复杂度与空间复杂度：

• 时间复杂度：O(n)，需要遍历数组。
• 空间复杂度：O(n)，存储哈希表。

适用场景：

适用于小规模数据，且有足够的内存空间支持额外的哈希表存储。

---

方法2：摩尔投票法（最佳选择）

摩尔投票法是一种高效的线性时间算法，专门用于解决多数元素问题。

算法步骤：

1. 初始化一个候选值 candidate 和计数器 count 为 0。
2. 遍历数组：
   • 如果当前计数为 0，将当前数字设置为候选值 candidate，并将计数器设置为 1。
   • 如果当前数字等于 candidate，计数器加 1。
   • 如果当前数字不等于 candidate，计数器减 1。
3. 遍历结束时，candidate 即为多数元素。

时间复杂度与空间复杂度：

• 时间复杂度：O(n)，只需遍历数组一次。
• 空间复杂度：O(1)，不需要额外的存储空间。

适用场景：

适用于任何规模的数据，且是本问题的最佳解决方案。

摩尔投票法原理解释

摩尔投票法（Boyer-Moore Voting Algorithm）是一种高效的算法，用于在一个数组中找到出现次数超过一半的元素（即 多数元素）。它的核心思想是通过一种计数机制，利用元素的多数性来进行筛选，最终在 O(n) 的时间复杂度内找到目标元素，并且空间复杂度为 O(1)。

问题背景：

在一个大小为 n 的数组中，假设存在一个数字的出现次数超过 n / 2，也就是说这个数字是多数元素。摩尔投票法的目标是找出这个元素。通过遍历数组一次并利用投票机制，我们能够在常数空间内找到这个元素。

摩尔投票法的基本原理：

1. 计数器： 摩尔投票法通过维护一个计数器来识别出现次数最多的元素。这个计数器会随着遍历数组而动态调整。

2. 选举过程：

   • 候选人：首先，我们假设某个元素是候选人（candidate），并初始化计数器为 0。
   • 投票规则：
     • 如果当前计数器为 0，选择当前元素作为新的候选人，并将计数器设置为 1。
     • 如果当前元素与候选人相同，计数器加 1。
     • 如果当前元素与候选人不同，计数器减 1。

   这种“投票”方式能够抵消一些非多数元素的干扰，并最终得到一个可能是多数元素的候选值。

3. 计数的终结： 当整个数组遍历完成后，candidate 就是候选的多数元素。由于多数元素的出现次数超过了数组长度的一半，这个候选元素一定就是多数元素。

详细步骤：

1. 初始化：

   • candidate（候选元素）初始化为一个任意值。
   • count（计数器）初始化为 0。

2. 遍历数组：

   • 对于数组中的每个元素：
     • 如果 count == 0，选择当前元素作为新的候选元素，并将计数器设为 1。
     • 如果当前元素等于 candidate，则增加计数器。
     • 如果当前元素与 candidate 不同，则减少计数器。

3. 返回结果：

   • 遍历结束后，candidate 即为数组中出现次数最多的元素。

直观解释：

假设数组中的多数元素出现次数超过了数组总长度的一半（n/2）。在摩尔投票法中，元素的“投票”机制确保了最多的元素最终会“胜出”。具体来说：

• 当遇到与当前候选人不同的元素时，我们会减去一个计数，导致非多数元素的出现机会被“削弱”。
• 只有当某个元素的出现次数非常高时，才可能在整个数组中最终成为唯一的候选人。

举例说明：

假设我们有数组：[3, 3, 4, 2, 4, 4, 2, 4, 4]。

• 第一步：candidate = 3, count = 0。
  • 看到第一个元素 3，count = 1，candidate = 3。
  • 看到第二个元素 3，count = 2，candidate = 3。
  • 看到第三个元素 4，count = 1，candidate = 3（count--）。
  • 看到第四个元素 2，count = 0，candidate = 2（count = 1）。
  • 看到第五个元素 4，count = 2，candidate = 4。
  • ...
  • 遍历完成后，candidate = 4 是多数元素。

为什么摩尔投票法有效？

• 由于题目保证了多数元素一定存在，并且它的出现次数超过数组的一半，因此，在摩尔投票法中，不同的元素相互“抵消”掉的次数是对等的，最终剩下的就是多数元素。
• 当计数器归零时，说明当前候选元素被其他元素“抵消”了，我们就将候选元素换成新的元素，从而不断减少非多数元素的影响，直到最后剩下的候选元素必然是多数元素。

---

摩尔投票法的优势

1. 时间复杂度 O(n)：

   • 只需要遍历数组一次，因此时间复杂度是 O(n)，其中 n 是数组的长度。

2. 空间复杂度 O(1)：

   • 只使用了两个变量：candidate 和 count，因此空间复杂度是 O(1)，不需要额外的空间。

3. 适用于大规模数据：

   • 在大规模数据中，摩尔投票法具有很高的效率，特别是在内存和空间限制较大的情况下，能够以最优的时间和空间复杂度完成任务。

---

步骤3：C++ 代码实现

使用摩尔投票法解决问题：

#include <iostream>
#include <vector>using namespace std;int solution(vector<int> array) {// 摩尔投票法int candidate = 0; // 候选元素int count = 0;      // 计数器// 第一次遍历，确定候选元素for (int num : array) {if (count == 0) {candidate = num; // 重置候选元素count = 1;       // 初始化计数器} else if (num == candidate) {count++; // 当前数字等于候选元素，计数器加1} else {count--; // 当前数字不等于候选元素，计数器减1}}// 此时candidate即为超过一半的数字，直接返回return candidate;
}int main() {// 测试用例cout << (solution({1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3) << endl; // 输出 1 (True)cout << (solution({5, 5, 5, 1, 2, 5, 5}) == 5) << endl;       // 输出 1 (True)cout << (solution({9, 9, 9, 9, 8, 9, 8, 8}) == 9) << endl;   // 输出 1 (True)return 0;
}

代码解释：

1. candidate：记录当前的候选多数元素。
2. count：记录候选元素的计数。
3. 第一遍遍历：通过计数器逻辑，找出候选元素。
4. 时间复杂度：O(n)，遍历数组一次。
5. 空间复杂度：O(1)，无额外空间开销。

---

步骤4：通过解决这个问题获得的启发

1. 算法设计的重要性：摩尔投票法以 O(n) 的时间和 O(1) 的空间高效解决了问题，体现了精妙的算法设计对效率的提升。
2. 多数性质的利用：当一个元素出现次数超过数组长度的一半时，不需要完全统计，利用其多数性质即可快速筛选。
3. 扩展应用：摩尔投票法不仅适用于确定多数元素，还可扩展到寻找多于 n/3 次出现的元素（需要两轮计数）。

---

步骤5：实际应用分析

实际场景：

1. 舆情分析：

   • 在一个讨论群中，找出被提及最多的关键词。例如，在一个由用户输入的评论数据中，快速筛选出出现频率超过一半的品牌名称或产品关键词。
   • 实现方法：
     • 将评论数据转化为数组形式，使用摩尔投票法筛选出最多的品牌关键词。

2. 传感器数据监测：

   • 在实时监测数据中，找出传感器的主流输出值，用于检测异常值。例如，某个值的输出频率异常高，可能表示系统进入了稳定状态。

3. 选举系统：

   • 在电子投票中，快速统计获胜的候选人（多数原则）。

实现示例：

在一个评论数据分析系统中，利用哈希表结合摩尔投票法，可以在多个评论字段中高效找出讨论最多的关键词。配合数据库或大数据平台，还可以实时生成分析报告，提升业务决策效率。