229. Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
- Time : O(nlogn)
- Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int t = nums.size() / 3;
sort(nums.begin(), nums.end());
for(int l = 0, r = 0; r < nums.size(); r++) {
while(r + 1< nums.size() and nums[r + 1] == nums[r]) r++;
while(l < r and nums[l] != nums[r]) l++;
if(r - l + 1 > t) res.push_back(nums[r]);
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, int> counter;
for(auto n : nums) counter[n]++;
int t = nums.size() / 3;
vector<int> res;
for(auto [k, v] : counter)
if(v > t) res.push_back(k);
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int t = nums.size() / 3;
int c1 = 0, c2 = 0, n1 = INT_MAX, n2 = INT_MAX;
for(auto n : nums) {
if(n1 == n) c1++;
else if(n2 == n) c2++;
else if(!c1) n1 = n, c1++;
else if(!c2) n2 = n, c2++;
else --c1,--c2;
}
c1 = c2 = 0;
for(auto n : nums) {
if(n1 == n) c1++;
else if(n2 == n) c2++;
}
if(c1 > t) res.push_back(n1);
if(c2 > t) res.push_back(n2);
return res;
}
};
|
