多数元素 II
难度:
标签:
题目描述
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3] 输出：[3]
示例 2：
输入：nums = [1] 输出：[1]
示例 3：
输入：nums = [1,2] 输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
代码结果
运行时间: 26 ms, 内存: 17.4 MB
/*
思路：
使用 Java Stream 和 Collectors.groupingBy 来统计每个数字出现的次数，
然后过滤出出现次数超过 ⌊ n/3 ⌋ 的元素。
*/
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.Arrays;
public class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
Map<Integer, Long> counts = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
return counts.entrySet().stream()
.filter(e -> e.getValue() > n / 3)
.map(Map.Entry::getKey)
.collect(Collectors.toList());
}
}解释
方法:
题解采用了摩尔投票算法的扩展版本，用于解决找出所有出现超过 ⌊ n/3 ⌋ 次的元素的问题。算法核心思想是维护两个候选元素以及它们的计数。遍历数组时，若当前元素等于其中一个候选元素，则增加该候选的计数；若不等于任何候选且有候选位置为空，则将当前元素设为新候选并计数为1；若两个候选都非空且当前元素与它们都不相等，则同时减少两个候选的计数。每次减计数时，若某候选的计数减到0，则释放该候选。最后，再次遍历数组以验证两个候选的真实计数是否超过 ⌊ n/3 ⌋，符合条件的则加入结果列表。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在摩尔投票算法中，为什么可以通过维护两个候选元素来确保找到所有满足条件的元素？
▷🦆
如果数组中没有任何元素的出现次数超过 ⌊n/3⌋ 次，算法是如何处理这种情况的？
▷🦆
算法中如何保证在第一次遍历结束后，被保留的候选元素确实是出现次数可能超过 ⌊n/3⌋ 的元素？
▷