Description
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?
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
n1 = n2 = 0
m1, m2 = 0, 1
for m in nums:
if m == m1:
n1 += 1
elif m == m2:
n2 += 1
elif n1 == 0:
m1, n1 = m, 1
elif n2 == 0:
m2, n2 = m, 1
else:
n1, n2 = n1 - 1, n2 - 1
return [m for m in [m1, m2] if nums.count(m) > len(nums) // 3]
|
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
33
34
35
36
37
38
39 | class Solution {
public List<Integer> majorityElement(int[] nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
for (int m : nums) {
if (m == m1) {
++n1;
} else if (m == m2) {
++n2;
} else if (n1 == 0) {
m1 = m;
++n1;
} else if (n2 == 0) {
m2 = m;
++n2;
} else {
--n1;
--n2;
}
}
List<Integer> ans = new ArrayList<>();
n1 = 0;
n2 = 0;
for (int m : nums) {
if (m == m1) {
++n1;
} else if (m == m2) {
++n2;
}
}
if (n1 > nums.length / 3) {
ans.add(m1);
}
if (n2 > nums.length / 3) {
ans.add(m2);
}
return ans;
}
}
|
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) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
for (int m : nums) {
if (m == m1)
++n1;
else if (m == m2)
++n2;
else if (n1 == 0) {
m1 = m;
++n1;
} else if (n2 == 0) {
m2 = m;
++n2;
} else {
--n1;
--n2;
}
}
vector<int> ans;
if (count(nums.begin(), nums.end(), m1) > nums.size() / 3) ans.push_back(m1);
if (count(nums.begin(), nums.end(), m2) > nums.size() / 3) ans.push_back(m2);
return ans;
}
};
|
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
33 | func majorityElement(nums []int) []int {
var n1, n2 int
m1, m2 := 0, 1
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
|