LeetCode/剑指 Offer 39. 数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

1 <= 数组长度 <= 50000

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题利用HashMap和经过排序后返回的中位数就是众数其实都比较好像，这个摩尔投票法真的秀的人头皮发麻，这里依次记录三种解法。

具体代码如下：

利用HashMap：

class Solution {
    public int majorityElement(int[] nums) {
        int num = nums.length / 2;
        int result = 0;
        Map<Integer, Integer> map = new HashMap<>();

      	//先遍历一边数组，将元素作为Key，元素出现次数作为Value
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

      	//题目说明只有一个数出现次数大于数组长度一半，找到直接返回即可
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            if (entry.getValue() > num) {
                result = entry.getKey();
              	break;
            }
        }
        return result;
    }
}

利用排序后中位数即是众树：

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

利用摩尔投票法：

摩尔投票法有两个推论

• 若记 众数 的票数为 +1 ，非众数 的票数为 -1 ，则一定有所有数字的 票数和 >0
• 若数组的前 $a$ 个数字的 票数和 =0 ，则 数组剩余 $(n-a)$ 个数字的 票数和一定仍 >0 ，即后 $(n-a)$ 个数字的 众数仍为 $x$。

所以，我们可以从第一个元素开始，假定第一个元素就是众数，我们每次遇到这个元素就+1​，其他元素就-1，如果votes==0，利用推论可以弃掉前面的元素，重新以当前元素开始，假定当前元素为众数继续向后遍历，最后返回x即是该数组众数。

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}