LeetCode：169. 多数元素

问题描述

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

示例

输入：nums = [3,2,3]
输出：3

输入：nums = [2,2,1,1,1,2,2]
输出：2

解题思路

1. 哈希表
   遍历数组，统计数量，找出多数元素。
2. 利用“多数元素”特性
   因为题中的多数元素出现次数必定大于n/2，所以 nums.length / 2位置的数一定是多数元素。
3. 分治
   这道题用分治需要一定的数学推理：
   如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
   假设 a是总数，但它既不是左半部分的众数，也不是右半部分的众数，那么 a 出现的次数少于 l / 2 + r / 2 次，其中 l 和 r 分别是左半部分和右半部分的长度。由于 l / 2 + r / 2 <= (l + r) / 2，说明 a 也不是数组 nums 的众数，因此出现了矛盾。

代码示例（JAVA）

1. 哈希表

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.get(num) == null ? 1 : map.get(num) + 1);
        }
        for (Integer item : map.keySet()) {
            if (map.get(item) > nums.length / 2) {
                return item;
            }
        }
        return 0;
    }
}

2. 利用“多数元素”特性

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

3. 分治

class Solution {
    public int majorityElement(int[] nums) {
        return recursion(nums, 0, nums.length - 1);
    }
    
    public int recursion(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        
        int mid = (left + right) / 2;
        int leftM = recursion(nums, left, mid);
        int rightM = recursion(nums, mid + 1, right);
        // 相同，说明这个就是众数
        if (leftM == rightM) {
            return leftM;
        }
        // 不同，比较一下这两个数在区间内出现的次数
        int leftCount = countInArray(nums, leftM, left, right);
        int rightCount = countInArray(nums, rightM, left, right);
        return leftCount > rightCount ? leftM : rightM;
    }
    
    public int countInArray(int[] nums, int num, int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }
}