多数元素
难度:
标签:
题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
代码结果
运行时间: 20 ms, 内存: 17.7 MB
/*
思路：使用 Java Stream，我们可以通过分组并统计每个元素出现的次数，然后找到出现次数最多的元素。
1. 将数组转换为流。
2. 使用 Collectors.groupingBy() 方法按元素分组，并统计每个元素出现的次数。
3. 找到出现次数最多的元素。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int majorityElement(int[] nums) {
return Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(e -> e, Collectors.counting()))
.entrySet()
.stream()
.max(Map.Entry.comparingByValue())
.get()
.getKey();
}
}解释
方法:
这个题解采用了摩尔投票算法。该算法的基本思想是用一种有效的方式找出列表中的多数元素。算法维护一个候选多数元素和一个计数器，遍历数组中的每个元素，当计数器为0时，将当前元素作为候选多数元素，并初始化计数器为1。如果遇到的元素等于当前候选元素，则计数器加1，否则计数器减1。由于多数元素的数量大于n/2，所以最后候选元素一定是多数元素。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
摩尔投票算法是如何确保最终候选元素确实是多数元素，尤其是在遇到计数器为零时频繁更换候选者的情况下？
▷🦆
在摩尔投票算法中，如果数组中的多数元素分布非常不均匀，这种情况会对算法的效率有何影响？
▷🦆
算法实现中提到的计数器增减操作，这种方法是否能处理所有的输入情况，例如所有元素均不相同的数组？
▷