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

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

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

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 投票算法
思路参考本题官方题解。

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;
}