LeetCode_Boyer-Moore 投票算法_中等_229.求众数 II

亦凉 2023-10-06 18:50 3阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。  
**进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。**

**示例 1：**  
输入：\[3,2,3\]  
输出：\[3\]

**示例 2：**  
输入：nums = \[1\]  
输出：\[1\]

**示例 3：**  
输入：\[1,1,1,3,3,2,2,2\]  
输出：\[1,2\]

**提示：**  
1 <= nums.length <= 5 \* 104  
\-109 <= nums\[i\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/majority-element-ii

## 2.思路 ##

（1）哈希表  
① 创建一个哈希表 hashMap，其中键 / 值为**nums中的整数 / 该整数目前出现的次数**，再创建一个保存结果的动态数组 res；  
② 遍历数组 nums，使用 put() 函数将当前整数nums\[i\]以及它目前出现的次数当作键值对添加到 hashMap 中（如果之前有添加过相同的Key，put() 方法会用新值替换旧值）；  
③ 使用 get() 获取当前整数出现的次数，如果次数大于 nums.length/3 且 res 中没有该整数，则将其添加到 res 中，并继续遍历。  
④ 遍历数组 nums 结束后最后返回 res 即可。

（2）Boyer-Moore 投票算法  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————哈希表
    public List<Integer> majorityElement(int[] nums) {
        
       int length = nums.length;
        ArrayList<Integer> res = new ArrayList<Integer>();
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < length; i++) {
        
            if (res.contains(nums[i])) {
        
                continue;
            }
            //put(Key,value):如果之前有添加过相同的Key，put()方法会用新值替换旧值，返回的是旧值
            //getOrDefault(key):获取指定key对应对value，如果找不到key，则返回设置的默认值
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
            if (hashMap.get(nums[i]) > length / 3 && !res.contains(nums[i])) {
        
                res.add(nums[i]);
            }
        }
        return res;
    }

//思路2————Boyer-Moore 投票算法，其时间复杂度为 O(n)、空间复杂度为 O(1)
    public List<Integer> majorityElement(int[] nums) {
        
        //利用反证法可以推断出满足题目条件的元素最多只有两个，我们设为 ele1 和 ele2
        int ele1 = 0;
        int ele2 = 0;
        //设 vote1 和 vote2 分别为 ele1 和 ele2 的赞成票数
        int vote1 = 0;
        int vote2 = 0;
        for (int num : nums) {
        
            if (vote1 > 0 && num == ele1) {
        
                //num 为第一个元素，则票数加1
                vote1++;
            } else if (vote2 > 0 && num == ele2) {
        
                //num 为第一个元素，则票数加1
                vote2++;
            } else if (vote1 == 0) {
        
                //选择第一个元素
                ele1 = num;
                vote1++;
            } else if (vote2 == 0) {
        
                //选择第二个元素
                ele2 = num;
                vote2++;
            } else {
        
                //三个元素 ele1、ele3、num 互不相同，则其票数减1
                vote1--;
                vote2--;
            }
        }
        //cnt1 和 cnt2 分别记录元素 ele1 和 ele2 出现的次数
        int cnt1 = 0;
        int cnt2 = 0;
        for (int num : nums) {
        
            if (vote1 > 0 && num == ele1) {
        
                cnt1++;
            }
            if (vote2 > 0 && num == ele2) {
        
                cnt2++;
            }
        }
        //检查元素出现的次数是否满足要求
        List<Integer> res = new ArrayList<>();
        if (vote1 > 0 && cnt1 > nums.length / 3) {
        
            res.add(ele1);
        } 
        if (vote2 > 0 && cnt2 > nums.length / 3) {
        
            res.add(ele2);
        }
        return res;
    }

[Link 1]: https://leetcode-cn.com/problems/majority-element-ii/solution/qiu-zhong-shu-ii-by-leetcode-solution-y1rn/