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

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 * 10⁴
-10⁹ <= nums[i] <= 10⁹

来源：力扣（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————哈希表
class Solution {
	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)
class Solution {
	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;
	}
}