友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
169. Majority Element
Boyer-Moore Voting Algorithm 这个算法好巧妙啊！简直妙不可言！
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3] Output: 3
Example 2:
Input: [2,2,1,1,1,2,2] Output: 2
思路分析
哈希计数法最易想到，摩尔投票法最妙！
-
一刷
-
二刷
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
/**
*Runtime: 2 ms, faster than 61.24% of Java online submissions for Majority Element.
*
* Memory Usage: 42.4 MB, less than 59.56% of Java online submissions for Majority Element.
*
* Boyer-Moore Voting Algorithm
*
* Copy from: https://leetcode.com/problems/majority-element/solution/[Majority Element solution - LeetCode]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-05 12:33
*/
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (0 == count) {
candidate = num;
}
count += candidate == num ? +1 : -1;
}
return candidate;
}
/**
* Runtime: 11 ms, faster than 45.56% of Java online submissions for Majority Element.
*
* Memory Usage: 40.6 MB, less than 99.26% of Java online submissions for Majority Element.
*/
public int majorityElementMap(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
Map<Integer, Integer> numToCountMap = new HashMap<>();
for (int num : nums) {
Integer count = numToCountMap.getOrDefault(num, 0);
numToCountMap.put(num, count + 1);
}
Map.Entry<Integer, Integer> result = null;
for (Map.Entry<Integer, Integer> entry : numToCountMap.entrySet()) {
if (result == null || result.getValue() < entry.getValue()) {
result = entry;
}
}
return result.getKey();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 摩尔投票法
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-20 21:38:37
*/
public int majorityElement(int[] nums) {
int votes = 0, x = nums[0];
for (int num : nums) {
if (votes == 0) {
x = num;
}
if (num == x) {
votes++;
} else {
votes--;
}
}
return x;
}