Links

0229. 求众数 II

题目地址(229. 求众数 II)

https://leetcode-cn.com/problems/majority-element-ii/

题目描述

给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
 
示例 1:
输入:[3,2,3]
输出:[3]
示例 2:
输入:nums = [1]
输出:[1]
示例 3:
输入:[1,1,1,3,3,2,2,2]
输出:[1,2]
 
提示:
1 <= nums.length <= 5 * 104
-10^9 <= nums[i] <= 10^9

前置知识

  • 摩尔投票法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题目和169.majority-element 很像。
我们仍然可以采取同样的方法 - “摩尔投票法”, 具体的思路可以参考上面的题目。
但是这里有一个不同的是这里的众数不再是超过1 / 2,而是超过1 / 3。题目也说明了,超过三分之一的有可能有多个
实际上就是 0,1,2 三种可能。
因此我们不能只用一个 counter 来解决了。 我们的思路是同时使用两个 counter,其他思路和上一道题目一样。
最后需要注意的是这两个 counter 只是出现次数最多的两个数字, 不一定都满足条件出现次数大于 1/3,因此最后我们需要进行过滤筛选。
这里画了一个图,大家可以感受一下:
229.majority-element-ii-1
229.majority-element-ii-1

关键点解析

  • 摩尔投票法
  • 两个 counter
  • 最后得到的只是出现次数最多的两个数字,有可能不满足出现次数大于 1/3

代码

代码支持:CPP,JS, Java, Python
CPP Code:
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int c1 = 0, c2 = 0, v1 = 0, v2 = 1;
for (int n : nums) {
if (v1 == n) ++c1;
else if (v2 == n) ++c2;
else if (!c1) v1 = n, ++c1;
else if (!c2) v2 = n, ++c2;
else --c1, --c2;
}
c1 = c2 = 0;
for (int n : nums) {
if (v1 == n) ++c1;
if (v2 == n) ++c2;
}
vector<int> v;
if (c1 > nums.size() / 3) v.push_back(v1);
if (c2 > nums.size() / 3) v.push_back(v2);
return v;
}
};
JS Code:
/*
* @lc app=leetcode id=229 lang=javascript
*
* [229] Majority Element II
*/
/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function (nums) {
const res = [];
const len = nums.length;
let n1 = null,
n2 = null,
cnt1 = 0,
cnt2 = 0;
for (let i = 0; i < len; i++) {
if (n1 === nums[i]) {
cnt1++;
} else if (n2 === nums[i]) {
cnt2++;
} else if (cnt1 === 0) {
n1 = nums[i];
cnt1++;
} else if (cnt2 === 0) {
n2 = nums[i];
cnt2++;
} else {
cnt1--;
cnt2--;
}
}
cnt1 = 0;
cnt2 = 0;
for (let i = 0; i < len; i++) {
if (n1 === nums[i]) {
cnt1++;
} else if (n2 === nums[i]) {
cnt2++;
}
}
if (cnt1 > (len / 3) >>> 0) {
res.push(n1);
}
if (cnt2 > (len / 3) >>> 0) {
res.push(n2);
}
return res;
};
Java Code:
/*
* @lc app=leetcode id=229 lang=java
*
* [229] Majority Element II
*/
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0)
return res;
int n1 = nums[0], n2 = nums[0], cnt1 = 0, cnt2 = 0, len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == n1)
cnt1++;
else if (nums[i] == n2)
cnt2++;
else if (cnt1 == 0) {
n1 = nums[i];
cnt1 = 1;
} else if (cnt2 == 0) {
n2 = nums[i];
cnt2 = 1;
} else {
cnt1--;
cnt2--;
}
}
cnt1 = 0;
cnt2 = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == n1)
cnt1++;
else if (nums[i] == n2)
cnt2++;
}
if (cnt1 > len / 3)
res.add(n1);
if (cnt2 > len / 3 && n1 != n2)
res.add(n2);
return res;
}
}
Python Code:
class Solution:
def majorityElement(self, nums):
c1 = c2 = 0
v1 = v2 = -1
for num in nums:
if num == v1: c1 += 1
elif num == v2: c2 += 1
elif c1 == 0:
c1 = 1
v1 = num
elif c2 == 0:
c2 = 1
v2 = num
else:
c1 -= 1
c2 -= 1
# check
c1 = c2 = 0
for num in nums:
if v1 == num: c1 += 1
if v2 == num: c2 += 1
ans = []
if c1 > len(nums)//3: ans.append(v1)
if c2 > len(nums)//3: ans.append(v2)
return list(set(ans))
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$

扩展

如果题目中 3 变成了 k,怎么解决?
大家可以自己思考一下,我这里给一个参考链接:https://leetcode.com/problems/majority-element-ii/discuss/63500/JAVA-Easy-Version-To-Understand!!!!!!!!!!!!/64925
这个实现说实话不是很好,大家可以优化一下。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。