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

水深无声 2023-10-06 18:47 49阅读 0赞

#### 目录 ####

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

## 1.题目 ##

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

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

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

n == nums.length  
1 <= n <= 5 \* 104  
\-109 <= nums\[i\] <= 109

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

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

## 2.思路 ##

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

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

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

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

[Link 1]: https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/