YCBlogs 算法笔记：找出数组中出现次数超过一半的数字——Boyer-Moore 投票与 Partition 快速选择详解

教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载本文基于 YCBlogs 仓库中 数组中出现次数超过一半的数字 的算法笔记展开完整讲解这道经典数组题的两种 O(n) 级解法基于 Partition 的快速选择算法与利用相互抵消特性的投票算法。读完本文你可以掌握多数元素Majority Element问题的核心证明思路、两种解法的手工推演过程、可完整运行的 Java 实现以及二次校验为什么必不可少等工程细节。一、题目要求与核心性质原题描述如下数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。举个例子帮助理解示意输入输入: [1, 2, 3, 2, 2, 2, 5, 2, 4] 数组长度 n 9出现次数超过一半意味着次数 9 / 2 4 数字 2 出现了 5 次满足条件 输出: 2在分析解法之前先明确题目隐含的两个核心性质它们是整个算法设计的理论根基存在性题目已保证满足条件的数字一定存在当然工程实现中仍需对非法输入做防御原文档代码中就保留了二次校验逻辑唯一性这样的数字最多只有一个。证明很简单——假设有两个数字 a 和 b 的出现次数都超过 n/2那么两者出现次数之和将严格大于 n与数组总长度为 n 矛盾。正是出现次数比其他所有数字出现次数之和还要多这一性质直接催生了下文解法二的投票思想。二、解法一基于 Partition 函数的 O(n) 算法2.1 为什么答案就是数组的中位数原文档对解法一的阐述是数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说这个数字就是统计学上的中位数即长度为 n 的数组中第 n/2 大的数字。这个结论可以进一步推演验证假设答案 x 出现了 k 次且 k n/2那么无论其余 n - k 个元素如何排布x 的占据区间必然覆盖索引 n/2 处。反证法来看若排序后中间位置不是 x则 x 必须全部落在前 n/2 或后 n/2 个位置中最多只能出现 n/2 次与 k n/2 矛盾。2.2 快速选择只排中位数所在的位置既然答案就是中位数那么是否需要对整个数组做 O(nlogn) 的排序不必。原文档接着给出了受快速排序启发的 O(n) 思路在随机快速排序算法中我们先在数组中随机选择一个数字然后调整数组中数字的顺序使得比选中的数字小的数字都排在它的左边比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是 n/2那么这个数字就是数组的中位数。如果它的下标大于 n/2那么中位数应该位于它的左边我们可以接着在它的左边部分的数组中查找。如果它的下标小于 n/2那么中位数应该位于它的右边我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程。关键在于Partition 一趟操作后pivot 已经落在了它在有序数组中的最终位置其余元素只需要比它大/小无需继续精确排序。这与完整快速排序的区别在于快速排序需要对 partition 之后的左右两部分都递归而快速选择QuickSelect每一层递归只进入目标下标 n/2 所在的那一侧因此平均时间复杂度是 O(n)。仓库中还有两篇笔记可以作为印证材料快速排序 一文中展示了双指针的 partition 过程——以 i 为界分割为两段的思想正是本题 partition 的基础最小的k个数 一文同样基于 Partition 函数解决第 k 个数字定位问题与本题第 n/2 个数字完全同构只是目标下标不同。原文档对解法一只有思路描述、未附代码下面基于原文描述的 Partition 过程补写一份完整实现作为解法一的可运行参考public class Test { /** * 快速选择找到数组第 middle 大索引为 middle的数字 * * param numbers 输入数组会被原地修改 * return 中位数 */ public static int moreThanHalfNumByPartition(int[] numbers) { if (numbers null || numbers.length 1) { throw new IllegalArgumentException(array length must large than 0); } int begin 0; int end numbers.length - 1; int middle numbers.length / 2; int index partition(numbers, begin, end); // 只递归目标所在的一侧而不是左右都排 while (index ! middle) { if (index middle) { end index - 1; } else { begin index 1; } index partition(numbers, begin, end); } return numbers[index]; } /** * 一趟 Partition小于 pivot 的元素全部移到左边 * pivot 落位在它在有序数组中的最终位置并返回该下标 * * param numbers 待调整数组 * param begin 本段起始下标 * param end 本段结束下标 * return pivot 的最终下标 */ private static int partition(int[] numbers, int begin, int end) { int pivot numbers[end]; // 原文档建议随机选 pivot 以降低最坏情况概率 int i begin; for (int j begin; j end; j) { if (numbers[j] pivot) { swap(numbers, i, j); i; } } swap(numbers, i, end); return i; } private static void swap(int[] numbers, int a, int b) { int temp numbers[a]; numbers[a] numbers[b]; numbers[b] temp; } }几点实现说明会修改原数组Partition 是原地调整输入数组的顺序会被打乱这与仓库中 最小的k个数 一文中只有可以修改输入数组时可用的结论一致平均 O(n)、最坏 O(n²)当数组已经有序且总是选中边界元素做 pivot 时每趟只能切掉一个元素退化为 O(n²)。原文档强调随机选择一个数字正是为了降低命中最坏情况的概率递归深度上述迭代写法每层搜索空间至少缩小一部分最坏情况下 while 循环 O(n) 次、每次 partition O(区间长度)整体与快速选择分析一致。三、解法二根据数组特点找出的 O(n) 投票算法3.1 核心思想相互抵消相比解法一需要调整数组顺序原文档给出的解法二不依赖排序只依赖多数元素次数 其余所有元素次数之和这一特点数组中有一个数字出现的次数超过数组长度的一半也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值一个是数组中的一个数字一个是次数。当我们遍历到下一个数字的时候如果下一个数字和我们之前保存的数字相同则次数加 1如果下一个数字和我们之前保存的数字不同则次数减 1。如果次数为零我们需要保存下一个数字并把次数设为 1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多那么要找的数字肯定是最后一次把次数设为 1 时对应的数字。这就是经典的Boyer-Moore 多数投票算法其本质是一个对消消去过程把当前候选数字与一个不同的数字两两配对抵消每抵消一对候选的次数计数器减 1计数器归零说明候选数字与其见过的对家数量打平候选必须更换。由于目标数字的总生命值出现次数严格大于所有对手生命值之和无论怎么两两对消最后幸存者一定包含目标数字而算法最终保留的候选正是最后一次把次数设为 1 时对应的数字。3.2 手工推演以原文档代码的逻辑初始result numbers[0]、count 1从第二个元素开始遍历对数组[1, 2, 3, 2, 2, 2, 5, 2, 4]逐步推演步骤 i当前元素分支判断resultcount初始-取首元素1112与 result 不同count--1023count 为 0换新候选3132与 result 不同count--3042count 为 0换新候选2152与 result 相同count2265与 result 不同count--2172与 result 相同count2284与 result 不同count--21遍历结束候选为2。可以看到第 2 步和第 3 步各更换了一次候选1 被 2 抵消、3 又被 2 抵消而 2 的出现次数5 次大于其余所有数字之和4 个最终它成为最后一次把次数设为 1 时对应的数字并幸存到最后——与原文档的结论完全吻合。3.3 为什么必须做第二次校验投票算法第一遍结束得到的只是一个候选而不是确定答案。反例输入[1, 2]时1 和 2 都没有出现超过一半但算法同样会跑出一个候选推演后 result 为 1。因此在题目不保证多数元素存在、或者输入不可信的场景下必须用第二遍遍历统计候选的真实出现次数只有count numbers.length / 2时才成立。原文档的实例代码正是这样处理的下面完整给出与仓库原文一致四、完整代码实现投票算法 二次校验以下代码来自仓库笔记 leetcode/01.数组/15.数组中出现次数超过一半的数字.md 的03.实例代码章节原文完整保留public class Test { /** * 题目数组中有一个数字出现的次数超过数组长度的一半请找出这个数字 * * param numbers 输入数组 * return 找到的数字 */ public static int moreThanHalfNum(int[] numbers) { // 输入校验 if (numbers null || numbers.length 1) { throw new IllegalArgumentException(array length must large than 0); } // 用于记录出现次数大于数组一半的数 int result numbers[0]; // 于当前记录的数不同的数的个数 int count 1; // 从第二个数开始向后找 for (int i 1; i numbers.length; i) { // 如果记数为0 if (count 0) { // 重新记录一个数假设它是出现次数大于数组一半的 result numbers[i]; // 记录统计值 count 1; } // 如果记录的值与统计值相等记数值增加 else if (result numbers[i]) { count; } // 如果不相同就减少相互抵消 else { count--; } } // 最后的result可能是出现次数大于数组一半长度的值 // 统计result的出现次数 count 0; for (int number : numbers) { if (result number) { count; } } // 如果出现次数大于数组的一半就返回对应的值 if (count numbers.length / 2) { return result; } // 否则输入异常 else { throw new IllegalArgumentException(invalid input); } } }对这段代码的关键点逐段拆解防御性输入校验numbers null || numbers.length 1时抛出IllegalArgumentException避免对空数组取numbers[0]触发IndexOutOfBoundsException第一遍投票注意三个分支的优先级——先判count 0换新候选再判相同则 count最后不同则 count--。这个顺序保证了 count 永远不会变成负数count的语义始终等于当前候选比不同数字多出来的净次数第二遍校验复用count变量重新统计候选的真实出现次数。这里用而不是比较numbers.length / 2整数除法与超过数组长度的一半的题意严格对应失败语义若输入中实际不存在多数元素则抛出IllegalArgumentException(invalid input)而不是静默返回一个错误答案——对面试场景这种要么答对、要么明确报错的设计比含糊其辞更有工程价值。五、两种解法的复杂度对比与适用场景维度解法一Partition 快速选择解法二Boyer-Moore 投票平均时间复杂度O(n)O(n)两遍线性扫描最坏时间复杂度O(n²)pivot 选择不当O(n)稳定空间复杂度O(1) 原地调整迭代写法O(1)是否修改原数组是否依赖条件多数元素存在中位数即答案候选筛选不需要前提但确认答案需要校验或题目保证数据形态适应性需要随机访问下标只要求可顺序读取适合流式/单遍扫描场景从源码结构看原文档把完整代码给了投票算法而非 Partition 算法并非偶然投票算法不修改原数组、最坏情况仍稳定 O(n)、且只需两个变量是这道题更硬核的标准答案Partition 解法的价值则在于它展示了中位数定位这一通用子问题——同样的代码框架把目标下标从n/2改成k就退化成了 最小的k个数 一文中讨论的 Partition 解法两者共享同一套 partition 心智模型。六、同族思想在仓库其他笔记中的延伸投票/抵消这类利用出现次数特征消去干扰项的思想在本仓库的算法笔记中并非孤例数组中只出现一次的数字其余元素均出现两次、求只出现一次的元素其异或解法相同值异或为 0、0 异或任意值为其本身与投票算法同属让重复项自我抵消的范式区别在于异或可以一次性给出确定答案无需二次校验快速排序 与 最小的k个数partition 过程是解法一的底层构件理解双指针分治后本题的只递归一侧改造就非常自然。七、总结出现次数超过数组长度一半的数字唯一存在且排序后必然位于中位数位置 n/2这是两种解法共同的事实基础Partition 快速选择通过每趟确定 pivot 最终位置、只递归目标所在侧把 O(nlogn) 排序降为平均 O(n) 的中位数定位但会破坏原数组且最坏 O(n²)Boyer-Moore 投票用相同加 1、不同减 1、归零换候选的对消规则以 O(1) 空间、稳定 O(n) 时间筛出候选且要找的数字肯定是最后一次把次数设为 1 时对应的数字投票算法的第一遍结果只是候选第二遍统计真实次数并配合count numbers.length / 2的判定不满足则抛异常是区分能跑通与正确性完备的关键工程细节。赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐YCBlogs 算法笔记数组中出现次数超过一半的数字——Boyer-Moore 投票多数元素算法详解YCBlogs 算法笔记数组中出现次数超过一半的数字——Boyer Moore 投票多数元素算法详解 本文基于 YCBlogs 仓库的 11.找出常用的数教程技术博客文档LeetCode-Go 题解229. Majority Element II —— Boyer-Moore 多数投票算法求出现次数超过 n/3 的元素LeetCode Go 题解229. Majority Element II —— Boyer Moore 多数投票算法求出现次数超过 n/3 的元素 导读示例工程Learn Next.js Hackathon经验分享如何赢得黑客马拉松的7个秘诀Learn Next.js Hackathon经验分享如何赢得黑客马拉松的7个秘诀 想要在Learn Next.js黑客马拉松中脱颖而出吗作为现代全栈Web上一篇OpCore SimplifyOpenCore EFI配置的技术民主化实践下一篇数据备份工具如何三步实现重要文件的永久保存创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考