友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
169. 多数元素
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
-
n == nums.length -
1 <= n <= 5 * 104 -
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
思路分析
哈希计数法最易想到，摩尔投票法最妙！
摩尔投票法更刺激的使用在 229. 多数元素 II。
-
一刷
-
二刷
-
三刷
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-29 22:22:09
*/
public int majorityElement(int[] nums) {
int num = 0;
int result = 0;
for (int i : nums) {
if (num == 0) {
num = 1;
result = i;
} else {
num += i == result ? +1 : -1;
}
}
return result;
}