摩尔投票算法
摩尔投票算法也可以叫做多数投票算法。
题
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在众数。
- 示例 1:
输入: [3,2,3]
输出: 3
- 示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
常规解法
- 遍历数组，并计数，找出出现次数大于 ⌊ n/2 ⌋ 的元素。
- 将数组排序，出现次数大于 ⌊ n/2 ⌋ 的元素必定在数组中间，返回nums[n/2]即可。
摩尔投票法求解
算法的时间和空间都很低，时间复杂度为O(n)，空间复杂度为O(1)
算法原理
每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。
- 算法在局部变量中定义一个序列元素(m)和一个计数器(count)，初始化的情况下计数器为1；
- 算法依次扫描序列中的元素，当处理元素x的时候，如果序列元素(m)和x相等，计数器(count)自增1；
- 如果不等计数器(count)自减1，并判断计数器是否为0，如果为0，那么将x赋值给m，然后将计数器(count)设置为1(或将x的下一位元素赋值给m，计数器(count)设为0)；
- 处理之后，最后存储的序列元素(m)，就是这个序列中最多的元素。 （如果不确定是否存储的元素m是最多的元素，还可以进行第二遍扫描判断是否为最多的元素）
伪码实现
初始化元素m=nums[0],计数器count=1;
for i = 1 : nums.length - 1
if m = nums[i]
count++
else
count--
if count = 0
m = numd[i + 1]
count = 0
return m
java实现
class Solution {
public int majorityElement(int[] nums) {
int count = 1, maj = nums[0];
for(int i = 1; i < nums.length; i++) {
if(maj == nums[i]) {
count++;
} else {
count--;
if(count == 0) {
maj = nums[i + 1];
count = 0;
}
}
}
return maj;
}
}
欢迎关注我的微信公众号
