[LeetCode] Majority Element II
LeetCode II Element
2023-09-14 09:06:21 时间
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋
times. The algorithm should run in linear time and in O(1) space.
解题思路
摩尔投票法。投票法的核心是找出两个候选众数进行投票,须要两遍遍历。第一遍历找出两个候选众数,第二遍遍历又一次投票验证这两个候选众数是否为众数就可以。
实现代码
C++:
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int m = 0, n = 0, cm = 0, cn = 0;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == m)
{
cm++;
}
else if (nums[i] == n)
{
cn++;
}
else if (cm == 0)
{
m = nums[i];
cm = 1;
}
else if (cn == 0)
{
n = nums[i];
cn = 1;
}
else
{
--cm;
--cn;
}
}
cm = cn = 0;
for (auto& a : nums)
{
if (a == m)
{
cm++;
}
else if (a== n)
{
cn++;
}
}
if (cm > nums.size() / 3)
{
res.push_back(m);
}
if (cn > nums.size() / 3)
{
res.push_back(n);
}
return res;
}
};
Java:
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
int m = 0, n = 0, cm = 0, cn = 0;
for (int a : nums) {
if (a == m) {
++cm;
} else if (a == n) {
++cn;
} else if (cm == 0) {
m = a;
cm = 1;
} else if (cn == 0) {
n = a;
cn = 1;
} else {
--cm;
--cn;
}
}
cm = cn = 0;
for (int a : nums){
if (a == m) {
++cm;
} else if (a == n) {
++cn;
}
}
if (cm > nums.length / 3) {
res.add(m);
}
if (cn > nums.length / 3) {
res.add(n);
}
return res;
}
}
相关文章
- Java实现 LeetCode 820 单词的压缩编码(暴力)
- Java实现 LeetCode 777 在LR字符串中交换相邻字符(分析题)
- Java实现 LeetCode 457 环形数组循环
- Java实现 LeetCode 219 存在重复元素 II(二)
- (LeetCode 41)First Missing Positive
- LeetCode(125):验证回文串
- LeetCode(107): 二叉树的层次遍历 II
- LeetCode(30):与所有单词相关联的字串
- (LeetCode 92)Reverse Linked List II
- LeetCode-729. 我的日程安排表 I【设计】
- 【LeetCode Python实现】剑指 Offer II 038. 每日温度(中等)单调栈
- 【LeetCode Python实现】737. 句子相似性 II(中等)
- Leetcode 299. 猜数字游戏
- leetcode 541. Reverse String II
- leetcode 598. Range Addition II
- leetcode 717. 1-bit and 2-bit Characters
- 【LeetCode】1514.概率最大的路径