LeetCode_Boyer-Moore 投票算法_简单_169.多数元素

1.题目

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

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

示例 2：
输入：[2,2,1,1,1,2,2]
输出：2

n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹

进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

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

2.思路

（1）排序
将数组 nums 中的所有元素排序后（无论是升序还是降序），那么下标为⌊ n/2 ⌋的元素一定是众数。

（2）哈希表

• 使用哈希表来存储每个元素以及出现的次数，其中键为元素，值为该元素出现的次数；
• 遍历数组 nums 并将数组中的每个元素加入哈希表中；
• 遍历哈希映射中的所有键值对，返回值最大的键即可。

（3）Boyer-Moore投票算法
思路参考本题官方题解。

3.代码实现（Java）

//思路1————排序
class Solution {
	public int majorityElement(int[] nums) {
	    Arrays.sort(nums);
	    return nums[nums.length / 2];
	}
}

//思路2————哈希表
class Solution {
	public int majorityElement(int[] nums) {
	    Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
	    for (int i = 0; i < nums.length; i++) {
	        if (hashMap.containsKey(nums[i])) {
	            hashMap.put(nums[i], hashMap.get(nums[i]) + 1);
	        } else {
	            hashMap.put(nums[i], 1);
	        }
	    }
	    int cnt = 1, elem = nums[0];
	    for (Integer key : hashMap.keySet()) {
	        int tmpVal = hashMap.get(key);
	        if (tmpVal > cnt) {
	            cnt = tmpVal;
	            elem = key;
	        }
	    }
	    return elem;
	}
}

//思路3————Boyer-Moore投票算法，其时间复杂度为 O(n)、空间复杂度为 O(1)
class Solution {
	public int majorityElement(int[] nums) {
	    /*
	    	把数组 nums 中相同的值看成同一个人
			设 candidate 为当前候选人(即多数元素)
			cnt 为当前候选人的票数，初始时为 0
		*/
	    int candidate = 0;
	    int cnt = 0;
	    //遍历数组 nums
	    for (int num : nums) {
	    	//当前候选人的票数为 0，发生换届选举
	        if (cnt == 0) {
	            candidate = num;
	        }
	        if (num == candidate) {
	        	//如果当前候选人是自己，则给自己投赞成票
	        	cnt++;
	        } else {
	        	//如果当前候选人不是自己，则给其投反对票
	        	cnt--;
			}
	    }
	    //如果 candidate 的赞成票数超过一半(即 cnt > 0)，最后成功当选(由题可知，候选人一定存在)
	    return candidate;
	}
}