[LeetCode] Majority Element II 求众数之二

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.

Hint:

1. How many majority elements could it possibly have?
2. Do you have a better hint? Suggest it!

class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int m = 0, n = 0, cm = 0, cn = 0;
for (auto &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 (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;
}
};

|
3月前
|
Java C++ Python
leetcode-501：二叉搜索树中的众数
leetcode-501：二叉搜索树中的众数
25 0
|
3月前
LeetCode刷题Day16——二叉搜索树（搜索、验证、最小绝对差、众数）

32 0
|
9月前
|

38 0
|
9月前
Leetcode 230. Kth Smallest Element in a BST

54 1
|
10月前

38 0
leetcode 501 二叉搜索树中的众数
leetcode 501 二叉搜索树中的众数
42 0
|

LeetCode 169. 多数元素 Majority Element
LeetCode 169. 多数元素 Majority Element
78 0
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix

86 0
|

LeetCode 229. Majority Element II

71 0
LeetCode 215. Kth Largest Element in an Array

68 0