想要精通算法和SQL的成长之路 - 摩尔投票法的运用
- 前言
- 一. 多数元素
- 1.1 摩尔投票法
- 二. 多数元素II
- 2.1 分析
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 多数元素
原题链接
1.1 摩尔投票法
简单来说,假设数组 num
的众数是 x
,数组长度为n
。
有两个推论:
- 我们有一个票数和为
sum
,若记众数的票数为+1
,非众数的票数为−1
,则一定有所有数字的票数和sum >0
。 - 如果数组的前
m
个数字的票数和为0,那么剩余的(n-m)
个数字的票数和一定> 0
,并且后面(n-m)
个数字中的众数依旧是x
。
那么针对本题目,求得的是多数元素,其出现次数超过数组元素个数的一半。思路如下:
- 我们设置当前众数为:
res
。初始化为数组第一元素。 - 设置当前票数和为:
vote
。初始化为0 - 遍历数组:如果票数和为0,更新众数为当前元素。
- 每次遍历,都对票数做统计,是众数,则+1,否则-1。
结果如下:
public int majorityElement(int[] nums) {
int res = nums[0], vote = 0;
for (int num : nums) {
if (vote == 0) {
res = num;
}
vote += (res == num) ? 1 : -1;
}
return res;
}
二. 多数元素II
原题链接
在原题的基础上,不再是求出现次数超过2分之一的多数元素了。而是三分之一。即本题的返回个数最多有两个。
2.1 分析
我们这里这里假设:有两个(并且最多只有两个)符合题目条件的元素:x 和 y。他们的票数分别是v1 和 v2。
- 利用摩尔投票法,确定两个候选数。因为我们这里假设的是2个都满足条件,但是实际情况可能只有一个或者没有。这里只是求得:出现次数最多的前两个数是哪几个(实际他们的出现次数却不知道)
- 最后再对这两个候选人做计数统计,统计他们分别出现的次数是多少,是否满足题目要求。
阶段一:摩尔投票阶段,决定出现次数最多的前两个数:
// 初始化两个候选数和对应票数
int x = nums[0], y = nums[0];
int v1 = 0, v2 = 0;
// 摩尔投票,求得出现次数最多的两个数
for (int num : nums) {
// 如果当前数和x一样
if (x == num) {
v1++;
continue;
}
// 如果当前数和x一样
if (y == num) {
v2++;
continue;
}
// 第一个候选票数为0了,那么当前数认定为第一个候选数
if (v1 == 0) {
x = num;
v1++;
continue;
}
// 第二个候选 同理
if (v2 == 0) {
y = num;
v2++;
continue;
}
// 否则,都不满足两个候选,两个候选的票数同时-1
v1--;
v2--;
}
这时候,我们拿到票数最多的两个元素,x和y。他们可能是同一个元素,也可能不是同一个元素。
接下来进入阶段二,统计票数阶段:
// 阶段二:统计票数阶段
v1 = 0;
v2 = 0;
for (int num : nums) {
if (num == x) {
v1++;
} else if (num == y) {
v2++;
}
}
注意:不能这么写:(两个数如果是同一个,那就重复了)
for (int num : nums) {
if (num == x) {
v1++;
}
if (num == y) {
v2++;
}
}
最后,判断他们的出现次数是否满足条件,满足则加入结果集,所有代码如下:
public List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
// 初始化两个候选数和对应票数
int x = nums[0], y = nums[0];
int v1 = 0, v2 = 0;
// 摩尔投票,求得出现次数最多的两个数
for (int num : nums) {
// 如果当前数和x一样
if (x == num) {
v1++;
continue;
}
// 如果当前数和x一样
if (y == num) {
v2++;
continue;
}
// 第一个候选票数为0了,那么当前数认定为第一个候选数
if (v1 == 0) {
x = num;
v1++;
continue;
}
// 第二个候选 同理
if (v2 == 0) {
y = num;
v2++;
continue;
}
// 否则,都不满足两个候选,两个候选的票数同时-1
v1--;
v2--;
}
// 阶段二:统计票数阶段
v1 = 0;
v2 = 0;
for (int num : nums) {
if (num == x) {
v1++;
} else if (num == y) {
v2++;
}
}
// 最后看看是否超过了三分之一
if (v1 > nums.length / 3) {
res.add(x);
}
if (v2 > nums.length / 3) {
res.add(y);
}
return res;
}