广州建网站加备案,重庆市建设工程信息网官网查询证书下载,在百度怎么做网站,百度开发平台问题描述
小R从班级中抽取了一些同学#xff0c;每位同学都会给出一个数字。已知在这些数字中#xff0c;某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。 测试样例
样例1#xff1a; 输入#xff1a;array [1, 3, 8, 2, 3, 1, 3, 3, 3] 输出…问题描述
小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。遍历结束时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。 看到第一个元素 3count 1candidate 3。看到第二个元素 3count 2candidate 3。看到第三个元素 4count 1candidate 3count--。看到第四个元素 2count 0candidate 2count 1。看到第五个元素 4count 2candidate 4。...遍历完成后candidate 4 是多数元素。
为什么摩尔投票法有效
由于题目保证了多数元素一定存在并且它的出现次数超过数组的一半因此在摩尔投票法中不同的元素相互“抵消”掉的次数是对等的最终剩下的就是多数元素。当计数器归零时说明当前候选元素被其他元素“抵消”了我们就将候选元素换成新的元素从而不断减少非多数元素的影响直到最后剩下的候选元素必然是多数元素。 摩尔投票法的优势 时间复杂度 O(n) 只需要遍历数组一次因此时间复杂度是 O(n)其中 n 是数组的长度。 空间复杂度 O(1) 只使用了两个变量candidate 和 count因此空间复杂度是 O(1)不需要额外的空间。 适用于大规模数据 在大规模数据中摩尔投票法具有很高的效率特别是在内存和空间限制较大的情况下能够以最优的时间和空间复杂度完成任务。 步骤3C 代码实现
使用摩尔投票法解决问题
#include iostream
#include vectorusing namespace std;int solution(vectorint 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实际应用分析
实际场景 舆情分析 在一个讨论群中找出被提及最多的关键词。例如在一个由用户输入的评论数据中快速筛选出出现频率超过一半的品牌名称或产品关键词。实现方法 将评论数据转化为数组形式使用摩尔投票法筛选出最多的品牌关键词。 传感器数据监测 在实时监测数据中找出传感器的主流输出值用于检测异常值。例如某个值的输出频率异常高可能表示系统进入了稳定状态。 选举系统 在电子投票中快速统计获胜的候选人多数原则。
实现示例
在一个评论数据分析系统中利用哈希表结合摩尔投票法可以在多个评论字段中高效找出讨论最多的关键词。配合数据库或大数据平台还可以实时生成分析报告提升业务决策效率。
