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?
多数元素 II。
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
思路
题意跟版本一差不多，区别在于这道题是在数组里找所有出现次数大于 1/3 数组长度的元素。
题目要求时间 O(n)，空间 O(1)，所以思路还是投票法。对于一个数组，最多只有两个元素的出现次数超过数组长度的三分之一，所以我们这里创建两个 candidate。首先我们将这两个 candidate 初始化为 0（因为有 test case 是数组长度小于 2 的所以不能设置为 nums[0], nums[1]），然后遍历数组，按照版本一的做法，统计这两个 candidate 的出现次数。这一题需要遍历两次 input 数组，第二次遍历的时候是在验证找到的两个 candidate 是否出现次数真的大于数组长度的三分之一，若是则加入结果集。
复杂度
时间O(n) - 题目要求
空间O(1) - 题目要求
代码
Java实现
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
40
41
42
43
44
45
46
47
48
| class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
int candidate1 = 0;
int candidate2 = 0;
int count1 = 0;
int count2 = 0;
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1++;
} else if (count2 == 0) {
candidate2 = num;
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
}
}
if (count1 > nums.length / 3) {
res.add(candidate1);
}
if (count2 > nums.length / 3) {
res.add(candidate2);
}
return res;
}
}
|
JavaScript实现
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
40
41
42
43
44
45
46
47
48
49
|
var majorityElement = function (nums) {
let res = [];
if (nums === null || nums.length === 0) {
return res;
}
let candidate1 = 0;
let candidate2 = 0;
let count1 = 0;
let count2 = 0;
for (let num of nums) {
if (num === candidate1) {
count1++;
} else if (num === candidate2) {
count2++;
} else if (count1 === 0) {
candidate1 = num;
count1++;
} else if (count2 === 0) {
candidate2 = num;
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (let num of nums) {
if (num === candidate1) {
count1++;
} else if (num === candidate2) {
count2++;
}
}
if (count1 > Math.floor(nums.length / 3)) {
res.push(candidate1);
}
if (count2 > Math.floor(nums.length / 3)) {
res.push(candidate2);
}
return res;
};
|
相关题目
1
2
| 169. Majority Element
229. Majority Element II
|