【LeetCode】- Java - 求众数

阳光穿透心脏的1/2处 2022-02-14 04:23 269阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

解法一：使用HashMap，记录每个元素出现的次数，参见代码如下：

import java.util.HashMap;
    import java.util.Map.Entry;
    class Solution {
        public int majorityElement(int[] nums) {
            int num = nums.length >> 1;
    
    		HashMap<Integer, Integer> map = new HashMap<>();
    		for (int i = 0; i < nums.length; i++) {
    			if (map.containsKey(nums[i])) {
    				map.put(nums[i], map.get(nums[i]) + 1);
    			} else {
    				map.put(nums[i], 1);
    			}
    		}
    
    		for (Entry<Integer, Integer> entry : map.entrySet()) {
    			if (entry.getValue() > num) {
    				return entry.getKey();
    			}
    		}
            
            return 0;
        }
    }

解法二：由题目假设，一定存在众数，可以证明众数只有一个，那排序之后，第 `⌊ n/2 ⌋``个元素便是需要寻找的众数，代码如下：`

private static void majorityElement(int[] nums) {
    		Arrays.sort(nums);
              //result便是需要寻找的众数
    		int result = nums[nums.length / 2];
    	}

解法三：摩尔投票法。由题目假设，众数一定存在，所以数组中至少有一半的元素相同，参见代码如下：

public int majorityElement(int[] nums) {
            // result表示众数，Count计数器
    		int result = 0, Count = 0;
    		for (int num : nums) {
    			if (Count == 0) {
    				
    				//重新选择众数
    				result = num;
    				Count++;
    			} else if (num == result) {
    				Count++;
    			} else {
    				Count--;
    			}
    		}
    		return result;
        }

解法四：此解法利用到了位（Bit）操作来解，将中位数按位来建立，从0到31位，每次统计下数组中该位上0和1的个数，如果1多，那么我们将结果res中该位变为1，最后累加出来的res就是过半数了，参见代码如下：

public int majorityElement(int[] nums) {
            int res = 0, n = nums.length;
    		for (int i = 0; i < 32; ++i) {
    
    			// ones表示第i位上1的个数，zeros表示第i为上为0的个数
    			int ones = 0, zeros = 0;
    			for (int num : nums) {
    
    				// 如果第i位上 1或者0的位数已经大于一半，便可确认该位上是1还是0
    				if (ones > n / 2 || zeros > n / 2)
    					break;
    
    				// 1 << i 表示1左移i位
    				if ((num & (1 << i)) != 0)
    					++ones;
    				else
    					++zeros;
    			}
    			if (ones > zeros)
    				res |= (1 << i);
    		}
    		return res;
        }

参考资料：

[https://leetcode.com/problems/majority-element/discuss/51613/O(n)-time-O(1)-space-fastest-solution][https_leetcode.com_problems_majority-element_discuss_51613_O_n_-time-O_1_-space-fastest-solution]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70]: /images/20220214/9bf145f8b8704322bcda03291d5e641e.png
[https_leetcode.com_problems_majority-element_discuss_51613_O_n_-time-O_1_-space-fastest-solution]: https://leetcode.com/problems/majority-element/discuss/51613/O%28n%29-time-O%281%29-space-fastest-solution