229. Majority Element II - medium
문제
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.
입출력 예
1
2
3
4
Example 1:
Input: [3,2,3]
Output: [3]
1
2
3
4
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
풀이
- Sort, Array
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
28
29
30
31
32
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
if (nums.empty()) {
return std::vector<int>();
}
std::vector<int> res;
int n = nums.size();
int N = n / 3;
std::sort(nums.begin(), nums.end());
int count = 1;
for (auto i = 0 ; i < n - 1 ; ++i) {
if (nums[i] == nums[i+1]) {
++count;
} else {
if (count > N) {
res.push_back(nums[i]);
}
count = 1;
}
}
if (count > N) {
res.push_back(nums[n-1]);
}
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
28
29
30
31
func majorityElement(nums []int) []int {
var res []int
var n = len(nums)
var N = n / 3
if n < 1 {
return res
}
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
var count = 1
for i := 0 ; i < n - 1 ; i++ {
if nums[i] == nums[i+1] {
count++
} else {
if count > N {
res = append(res, nums[i])
}
count = 1
}
}
if count > N {
res = append(res, nums[n-1])
}
return res
}