摩尔投票法
提问: 给定一个int型数组,找出该数组中出现次数最多的int值。
解决方案: 遍历该数组,统计每个int值出现次数,再遍历该集合,取出出现次数最大的int值。
这算是一个比较经典的解决办法,其中可能会用到Map来做统计。如果不使用Map,则时间复杂度会超过线性复杂度。除此之外,也没有什么特别好的办法。
今天在leetcode上遇到这样一道题目,
提问: 给定一个int型数组,找出该数组中出现次数大于数组长度一半的int值。
解决方案: 遍历该数组,统计每个int值出现次数,再遍历该集合,找出出现次数大于数组长度一半的int值。
同样的,该解决办法也要求使用Map,否则无法达到线性的时间复杂度。
那么对于这个问题,有没有什么不使用Map的线性算法呢?
答案就是今天我们要提到的摩尔投票法。利用该算法来解决这个问题,我们可以达到线性的时间复杂度以及常量级的空间复杂度。
首先我们注意到这样一个现象: 在任何数组中,出现次数大于该数组长度一半的值只能有一个。
通过数学知识,我们可以证明它的正确性,但是这并不在我们这篇博客里涉及。
摩尔投票法的基本思想很简单,在每一轮投票过程中,从数组中找出一对不同的元素,将其从数组中删除。这样不断的删除直到无法再进行投票,如果数组为空,则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素,那么这个元素则可能为目标元素。
那么有没有可能出现最后有两种或两种以上元素呢?根据定义,这是不可能的,因为如果出现这种情况,则代表我们可以继续一轮投票。因此,最终只能是剩下零个或一个元素。
在算法执行过程中,我们使用常量空间实时记录一个候选元素c以及其出现次数f(c),c即为当前阶段出现次数超过半数的元素。根据这样的定义,我们也可以将摩尔投票法看作是一种动态规划算法。
程序开始之前,元素c为空,f(c)=0。遍历数组A:
* 如果f(c)为0,表示截至到当前子数组,并没有候选元素。也就是说之前的遍历过程中并没有找到超过半数的元素。那么,如果超过半数的元素c存在,那么c在剩下的子数组中,出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
* 如果当前元素A[i] == c, 那么f(c) += 1。(没有找到不同元素,只需要把相同元素累计起来)
* 如果当前元素A[i] != c,那么f(c) -= 1 (相当于删除1个c),不对A[i]做任何处理(相当于删除A[i])
如果遍历结束之后,f(c)不为0,则找到可能元素。
再次遍历一遍数组,记录c真正出现的次数,从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n),而由于并不需要真的删除数组元素,我们也并不需要额外的空间来保存原始数组,空间复杂度为O(1)。
看java代码示例,为了保证每一步骤的清晰性,代码没有经过优化。
/** * 算法基础:摩尔投票法 * @param nums * @return */ public int majorityElement(int[] nums) { int majority = -1; int count = 0; for (int num : nums) { if (count == 0) { majority = num; count++; } else { if (majority == num) { count++; } else { count--; } } } int counter = 0; if (count <= 0) { return -1; } else { for (int num : nums) { if (num == majority) counter ++; } } if (counter > nums.length / 2) { return majority; } return -1; }
其实这样的算法也可以衍生到其它频率的问题上,比如说,找出所有出现次数大于n/3的元素。同样可以以线性时间复杂度以及常量空间复杂度来实现。
相关推荐
勇于摩尔投票法的一个小Demo,应用场景不广,但是是一个有趣的算法
#资源达人分享计划#
(完整版)凝固点降低法测定摩尔质量的思考题及答案.pdf
解题思路摩尔投票法,这个方法真的很有意思,大致做法就是遍历整个数组,用 res 记录自己遇到的第一个元素,并维护一个初始值为 1 的 count ,在之后的遍历
摩尔投票法 f: 0 f: INF 摩尔投票法 。。 还是不会啊,这种问题 f: INF 想了半天想出了要求因子为5的个数,但是没想出该怎么统计 f: INF 计算质数,需要用到缓存加速,实在是想不到啊 f: 0 f: 0 go 的堆写的就是蛋疼...
粘度法测定高聚物的相对摩尔质量实验报告.doc
凝固点下降法测定摩尔质量实验报告参考.doc
详细的摩尔库伦代码,应该对初学者的本构模型二次开发有一定的参考意义
物化实验报告_凝固点降低法测定摩尔质量.doc
在文件qiexian.m中输入两个摩尔圆的坐标即可画出莫尔圆,并求出两圆的切线
本文讲解了超越摩尔的概念和意义,还有一些发展趋势和影响
Adobe Photoshop 的Demoirize 插件可通过三种不同的过滤模式去除图像中的摩尔条纹
(摩尔投票法,注意判断是否存在超过一半的数字) (重要小顶堆) (重要,大顶堆+小顶堆) (重要,动态规划,分治法再做) (sort自定义排序) (动态规划,小顶堆) (归并排序的思想) (二分查找) 0〜n ...
万家摩尔,一个电商例子 万家摩尔,一个电商例子
"摩尔投票法"。 LCA 二叉树最近共同祖先问题. 递归结题的思路,在左子树、右子树查找两个节点,可能的结果有: 该节点就是其中的一个节点,则返回该节点 两个节点都不在左边,那么肯定都在右边,返回右边找到的节点 ...
本源代码来自ABAQUS在隧道及地下工程中的应用一书,供大家学习使用。
java lru leetcode README leetcode题目分类 1.数组 2.Linked List (注意如果是两个Integer类型进行比较要用equals,有赞...摩尔投票法 核心就是对拼消耗) 9.深度优先搜索和广度优先搜索 每日一题 10.贪心算法 11.
日常实践 代码更新: 2020_11_13:质数判断;... 2020_11_20:寻找整型分布中出现次数大于多个元素数一半的元素(摩尔投票法) 2020_11_21:杨辉三角;找杀手 2020_11_22:大小端判断;简易计算器;跳远排名 2020
的,更好的解决办法是摩尔投票法,即对拼消耗,O(n) 时间复杂度。 class Solution { public int majorityElement(int[] nums) { int result = nums[0]; int mod = 1; for (int i = 1; i < nums.length; i++) { if...