题目描述
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：nums = [1,2]
输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(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 {
n2++
} else if n1 == 0 {
m1, n1 = m, 1
} else if n2 == 0 {
m2, n2 = m, 1
} else {
n1, n2 = n1-1, n2-1
}
}
n1, n2 = 0, 0
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
n2++
}
}
var ans []int
if n1 > len(nums)/3 {
ans = append(ans, m1)
}
if n2 > len(nums)/3 {
ans = append(ans, 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
34
35
36 | public class Solution {
public IList<int> MajorityElement(int[] nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
foreach (int m in 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;
}
}
var ans = new List<int>();
ans.Add(m1);
ans.Add(m2);
return ans.Where(m => nums.Count(n => n == m) > nums.Length / 3).ToList();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
/**
* @param Integer[] $nums
* @return Integer[]
*/
function majorityElement($nums) {
$rs = [];
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
$hashmap[$nums[$i]] += 1;
if ($hashmap[$nums[$i]] > $n / 3) {
array_push($rs, $nums[$i]);
}
}
return array_unique($rs);
}
}
|