169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
1
2
输入：nums = [3,2,3]
输出：3
示例 2：
1
2
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
写了一个方法，通过了，但是不是很快：
这个方法的时间复杂度是O(n)，空间复杂度也是O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int majorityElement(int[] nums) {
int N = nums.length;
if (N == 1) return nums[0];
int range = N / 2;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < N; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], 1);
} else {
int time = map.get(nums[i]);
map.put(nums[i], ++time);
if (time > range) {
return nums[i];
}
}
}
return -1;
}
}
使用 HashMap 记录每个元素的出现次数：
- 遍历数组，对于每个元素：
- 如果 HashMap 中没有该元素，加入并设置次数为 1。
- 如果已有该元素，取出当前次数，递增后更新，并检查是否超过 range。
- 如果找到次数超过 range 的元素，立即返回该元素。
当前算法使用 HashMap 统计频率，虽然时间复杂度已经是线性的 O(N)，但仍有优化空间
Boyer-Moore 投票算法：
注：这个算法除了力扣169，还有LeetCode 229。可以一起尝试下
- 基本思想：多数元素出现次数超过一半，因此可以用“抵消”策略。即维护一个候选元素和计数器：
- 遇到相同元素，计数器加 1。
- 遇到不同元素，计数器减 1。
- 当计数器为 0 时，替换候选元素。
- 因为多数元素超过一半，最终留下的候选必然是多数元素。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int majorityElement(int[] nums) {
int N = nums.length;
if (N == 1) return nums[0];
int vote = nums[0];//备选元素
int count = 1;//计数器
for (int i = 1;i < N;i++){
if (count == 0){
vote = nums[i];
count = 1;
}else if (nums[i] == vote){
count++;
}else {
count--;
}
}
return vote;
}
}
更加简洁的写法（参考他人）：
1
2
3
4
5
6
7
8
9
10
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for (int num : nums){
if (votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
}
