下面2道已经做过，记录1150和2404两道题，这4道题都是和摩尔投票算法相关的。
1150. 检查一个数是否在数组中占绝大多数
1
2
3
4
5
6
7
8
9
class Solution {
public boolean isMajorityElement(int[] nums, int target) {
int count = 0;// 计数器
for (int i : nums) {
if (target == i) count++;
}
return count > nums.length / 2;
}
}
2404. 出现最频繁的偶数元素
解法1:HashMap
写了个很垃圾的方法：
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 int mostFrequentEven(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
if (n % 2 == 0 && !map.containsKey(n)) {
map.put(n, 1);
} else if (map.containsKey(n)) {
map.put(n, map.get(n) + 1);
}
}
int max = 0;
List<Integer> res = new ArrayList<>();
for (Integer key : map.keySet()) {
int c = map.get(key);
if (c > max) {
max = c;
res.clear();
res.add(key);
} else if (c == max) {
res.add(key);
}
}
if (res.size() > 1) return Collections.min(res);
if (res.size() == 1) return res.get(0);
return -1; // 全部都是奇数
}
}
我看到一个和我一样用HashMap的，但是比我简洁：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int mostFrequentEven(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
if (x % 2 == 0) {
cnt.merge(x, 1, Integer::sum);
}
}
int ans = -1, mx = 0;
for (var e : cnt.entrySet()) {
int x = e.getKey(), v = e.getValue();
if (mx < v || (mx == v && ans > x)) {
ans = x;
mx = v;
}
}
return ans;
}
}
注：
1.若 x 为偶数，使用 merge 方法更新 cnt：
- 若键 x 不存在，则插入键值对 (x, 1)。
- 若键 x 已存在，则将其值与 1 相加（通过 Integer::sum 函数）。
2.比较逻辑：
- 若当前频率 v 大于最大频率 mx，更新 ans 为 x，mx 为 v。
- 若 v 等于 mx 且当前 x 小于 ans，更新 ans 为 x（确保返回最小值）。
解法2:单次遍历+数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int mostFrequentEven(int[] nums) {
int[] arr = new int[50001];
int ans = -1, mx = 0;
for (int i : nums) {
if (i % 2 == 0) {
int freq = ++arr[i / 2];
if (freq > mx || (freq == mx && i < ans)){
mx = freq;
ans = i;
}
}
}
return ans;
}
}
注：
由于元素值范围固定且较小（( 0 ) 到 10^5），可用固定大小的数组替代 HashMap，仅记录偶数频率：
- 数组大小为
10^5 / 2 + 1 = 50001（仅偶数）。
