摩尔投票算法
起因
刷leetcode_169 数组tag的时候有道题
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于
⌊ n/2 ⌋
的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。
一般来讲大概第一反应是暴力算法,出现次数累加看谁超过了总数量的一半即可输出结果…方法可行可惜效率太低,时间复杂度达到O(n^2^),那有没有线性复杂度的解决办法.
Boyer-Moore 投票算法
少数服从多数的摩尔投票算法就是其中之一的解决之道
这里按照找众数的题来解释算法的实现过程:
1 | nums:[1,1,2,1,2,2,2,1,2] |
比如说该数组nums,显然众数是 2
首先我们设置一个候选众数,初始为第一个元素nums[0]
我们设置一个计数器count,初始值为1,其规则是遇到与候选众数相同的数是+1,不同-1
当count值为0时,我们让候选众数变为下一位,并将count重置为1,继续上述规则
1 | [1,1,2,1,2 | 2,1,2] |
分隔处为count归0时,此时候选众数变为下一位2,count值回到1
显然在这前面这一过程中,随着count值的递增递减到归0我们消耗了相同数量的非众数和众数
这是我认为投票算法最重要的思想,通过这样的往复,遍历结束后,最终候选众数即为该数组众数
代码实现
附上用C实现上述例子:
1 | int majorityElement(int* nums, int numsSize){ |
Asahi
2019.7.5
at 530