LeetCode刷题之HOT100之多数元素

2024/5/21 起床走到阳台，外面绵柔细雨，手探出去，似乎感受不到。刚到实验室，窗外声音放大，雨大了。昨天的两题任务中断了，由于下雨加晚上有课。这样似乎也好，不让我有一种被强迫的感觉，随心所欲些也好，做题！

1、题目描述

2、逻辑分析

题目要求就是找出在数组中数量占比大于整个数组长度n的一半的元素。我的思路：第一步：将数组里面的元素遍历记录出现的个数；第二步：将他们与n/2比较。

在这里我突然又想到：数量超过一般的元素具有唯一性，那么算法可不可以优化一下：将数组中存在数量最多的元素来跟n/2比较。这里使用哈希表。

3、代码演示

public int majorityElement(int[] nums) {// 使用一个Map来统计每个数字出现的次数  Map<Integer, Integer> counts = countNums(nums);// 定义一个变量来存储多数元素及其计数，初始化为nullMap.Entry<Integer, Integer> majorEntry = null;// 遍历Map中的每个元素for(Map.Entry<Integer, Integer> entry : counts.entrySet()){// 如果majorEntry是null，或者当前元素的计数大于majorEntry的计数if(majorEntry == null || entry.getValue() > majorEntry.getValue()){// 更新majorEntry为当前元素 majorEntry = entry;}}// 返回多数元素的键（即多数元素本身）return majorEntry.getKey();}// 定义一个私有方法，用于统计数组中每个数字的出现次数并返回结果Map private Map<Integer,Integer> countNums (int [] nums){// 创建一个HashMap来存储数字及其出现次数Map<Integer , Integer> counts = new HashMap<Integer, Integer>();for(int num : nums){// 如果该数字尚未在Map中出现过if(!counts.containsKey(num)){// 将该数字添加到Map中，并设置其出现次数为1counts.put(num,1);}else{// 如果该数字已在Map中出现过，则增加其出现次数counts.put(num,counts.get(num) + 1);}}// 返回存储了每个数字及其出现次数的Mapreturn counts;}

这里使用了哈希表将元素作为键，元素的数量作为值。然后遍历哈希表，找到键值对中值最大的元素，最后返回该元素。技术难点是对哈希表还是不够熟练，特别是map.entry这里，都不知道还可以这样用。

时间复杂度：O(n)，空间复杂度：O(n)。

这道题的解法好多啊，还有：排序、随机化、分治、Boyer-Moore 投票算法。

下面我们主要来说一下最后一个Boyer-Moore 投票算法，也称为摩尔投票算法。官方的思路解法太过于官方，这里选取了其他题解：

下面直接看代码：

public int majorityElement(int[] nums) {// 计数器，用于追踪当前候选的多数元素的数量int count = 0;// 候选的多数元素  Integer candidate = null;// 遍历数组中的每个元素for(int num : nums){// 如果计数器为0，则更新候选的多数元素为当前遍历到的元素if(count == 0){candidate = num;}// 如果当前元素与候选的多数元素相同，则计数器加1；否则减1 count += (num == candidate) ? 1 : -1;}// 返回候选的多数元素return candidate;}

时间复杂度：O(n)，空间复杂度：O(1)。