问题描述
小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
的数字。
限制与边界条件:
- 数组中保证一定存在满足条件的数字。
- 数组长度
n
的范围未明确给出,但假设为合理范围(如1 <= n <= 10^6
)。 - 只需要输出符合条件的任意一个数字,不需要处理无解的情况。
问题性质:
- 根据题意,某个数字的出现次数超过总数的一半,称为 多数元素。
- 这种问题可以通过经典的算法(如摩尔投票法)高效解决,而不需要使用暴力计数法。
步骤2:算法设计与分析
方法1:哈希表计数
- 使用哈希表统计每个数字的出现次数。
- 遍历数组,当某个数字的出现次数超过
n / 2
时返回该数字。
时间复杂度与空间复杂度:
- 时间复杂度:O(n),需要遍历数组。
- 空间复杂度:O(n),存储哈希表。
适用场景:
适用于小规模数据,且有足够的内存空间支持额外的哈希表存储。
方法2:摩尔投票法(最佳选择)
摩尔投票法是一种高效的线性时间算法,专门用于解决多数元素问题。
算法步骤:
- 初始化一个候选值
candidate
和计数器count
为 0。 - 遍历数组:
- 如果当前计数为 0,将当前数字设置为候选值
candidate
,并将计数器设置为 1。 - 如果当前数字等于
candidate
,计数器加 1。 - 如果当前数字不等于
candidate
,计数器减 1。
- 如果当前计数为 0,将当前数字设置为候选值
- 遍历结束时,
candidate
即为多数元素。
时间复杂度与空间复杂度:
- 时间复杂度:O(n),只需遍历数组一次。
- 空间复杂度:O(1),不需要额外的存储空间。
适用场景:
适用于任何规模的数据,且是本问题的最佳解决方案。
摩尔投票法原理解释
摩尔投票法(Boyer-Moore Voting Algorithm)是一种高效的算法,用于在一个数组中找到出现次数超过一半的元素(即 多数元素)。它的核心思想是通过一种计数机制,利用元素的多数性来进行筛选,最终在 O(n) 的时间复杂度内找到目标元素,并且空间复杂度为 O(1)。
问题背景:
在一个大小为 n
的数组中,假设存在一个数字的出现次数超过 n / 2
,也就是说这个数字是多数元素。摩尔投票法的目标是找出这个元素。通过遍历数组一次并利用投票机制,我们能够在常数空间内找到这个元素。
摩尔投票法的基本原理:
-
计数器: 摩尔投票法通过维护一个计数器来识别出现次数最多的元素。这个计数器会随着遍历数组而动态调整。
-
选举过程:
- 候选人:首先,我们假设某个元素是候选人(
candidate
),并初始化计数器为 0。 - 投票规则:
- 如果当前计数器为 0,选择当前元素作为新的候选人,并将计数器设置为 1。
- 如果当前元素与候选人相同,计数器加 1。
- 如果当前元素与候选人不同,计数器减 1。
这种“投票”方式能够抵消一些非多数元素的干扰,并最终得到一个可能是多数元素的候选值。
- 候选人:首先,我们假设某个元素是候选人(
-
计数的终结: 当整个数组遍历完成后,
candidate
就是候选的多数元素。由于多数元素的出现次数超过了数组长度的一半,这个候选元素一定就是多数元素。
详细步骤:
-
初始化:
candidate
(候选元素)初始化为一个任意值。count
(计数器)初始化为 0。
-
遍历数组:
- 对于数组中的每个元素:
- 如果
count == 0
,选择当前元素作为新的候选元素,并将计数器设为 1。 - 如果当前元素等于
candidate
,则增加计数器。 - 如果当前元素与
candidate
不同,则减少计数器。
- 如果
- 对于数组中的每个元素:
-
返回结果:
- 遍历结束后,
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
是多数元素。
- 看到第一个元素
为什么摩尔投票法有效?
- 由于题目保证了多数元素一定存在,并且它的出现次数超过数组的一半,因此,在摩尔投票法中,不同的元素相互“抵消”掉的次数是对等的,最终剩下的就是多数元素。
- 当计数器归零时,说明当前候选元素被其他元素“抵消”了,我们就将候选元素换成新的元素,从而不断减少非多数元素的影响,直到最后剩下的候选元素必然是多数元素。
摩尔投票法的优势
-
时间复杂度 O(n):
- 只需要遍历数组一次,因此时间复杂度是 O(n),其中 n 是数组的长度。
-
空间复杂度 O(1):
- 只使用了两个变量:
candidate
和count
,因此空间复杂度是 O(1),不需要额外的空间。
- 只使用了两个变量:
-
适用于大规模数据:
- 在大规模数据中,摩尔投票法具有很高的效率,特别是在内存和空间限制较大的情况下,能够以最优的时间和空间复杂度完成任务。
步骤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;
}
代码解释:
candidate
:记录当前的候选多数元素。count
:记录候选元素的计数。- 第一遍遍历:通过计数器逻辑,找出候选元素。
- 时间复杂度:O(n),遍历数组一次。
- 空间复杂度:O(1),无额外空间开销。
步骤4:通过解决这个问题获得的启发
- 算法设计的重要性:摩尔投票法以 O(n) 的时间和 O(1) 的空间高效解决了问题,体现了精妙的算法设计对效率的提升。
- 多数性质的利用:当一个元素出现次数超过数组长度的一半时,不需要完全统计,利用其多数性质即可快速筛选。
- 扩展应用:摩尔投票法不仅适用于确定多数元素,还可扩展到寻找多于 n/3 次出现的元素(需要两轮计数)。
步骤5:实际应用分析
实际场景:
-
舆情分析:
- 在一个讨论群中,找出被提及最多的关键词。例如,在一个由用户输入的评论数据中,快速筛选出出现频率超过一半的品牌名称或产品关键词。
- 实现方法:
- 将评论数据转化为数组形式,使用摩尔投票法筛选出最多的品牌关键词。
-
传感器数据监测:
- 在实时监测数据中,找出传感器的主流输出值,用于检测异常值。例如,某个值的输出频率异常高,可能表示系统进入了稳定状态。
-
选举系统:
- 在电子投票中,快速统计获胜的候选人(多数原则)。
实现示例:
在一个评论数据分析系统中,利用哈希表结合摩尔投票法,可以在多个评论字段中高效找出讨论最多的关键词。配合数据库或大数据平台,还可以实时生成分析报告,提升业务决策效率。