229. Majority Element II
Đề Bài
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
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]
Constraints:
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
Lời Giải
C++
0229-majority-element-ii.cpp
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
int candidate1, candidate2;
int vote1 = 0, vote2 = 0;
for (int num : nums) {
if (num == candidate1) {
vote1++;
}
else if (num == candidate2) {
vote2++;
}
else if (!vote1) {
candidate1 = num;
vote1 = 1;
}
else if (!vote2) {
candidate2 = num;
vote2 = 1;
}
else {
vote1--;
vote2--;
}
}
vector<int> ans;
vote1 = vote2 = 0;
for (int num : nums) {
if (num == candidate1) {
vote1++;
}
else if (num == candidate2) {
vote2++;
}
}
int d = n / 3;
if (vote1 > d) {
ans.push_back(candidate1);
}
if (vote2 > d) {
ans.push_back(candidate2);
}
return ans;
}
};