229. Majority Element II
1. Description
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
2. Example
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
3. Constraints
- 1 <= nums.length <= $5 * 10^4$
- $-10^9$ <= nums[i] <= $10^9$
4. Follow Up
Could you solve the problem in linear time and in O(1) space?
5. Solutions
Moore Vote
n = nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
vector<int> majorityElement(vector<int> &nums) {
// we have at most 2 valid answers
array<pair<int, int>, 2> num_and_count{{{0, 0}, {0, 0}}};
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == num_and_count[0].first) {
++num_and_count[0].second;
} else if (nums[i] == num_and_count[1].first) {
++num_and_count[1].second;
} else if (num_and_count[0].second == 0) {
num_and_count[0] = {nums[i], 1};
} else if (num_and_count[1].second == 0) {
num_and_count[1] = {nums[i], 1};
} else {
--num_and_count[0].second;
--num_and_count[1].second;
}
}
vector<int> result;
for (int i = 0; i < num_and_count.size(); ++i) {
int candidate = num_and_count[i].first;
if (result.empty() || candidate != result[0]) {
int candidate_count = count(nums.begin(), nums.end(), candidate);
if (candidate_count > nums.size() / 3) {
result.push_back(candidate);
}
}
}
return result;
}
};