题目描述

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

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

示例 1:

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

题解

哈希表

先使用哈希表这个效率不高但是直观的方法, 遍历整个数组, 将每个元素出现的次数记录下来, 一旦超过总数的一半立即返回

public int majorityElement(int[] nums) {
    if (nums.length==1)
        return nums[0];
    HashMap<Integer, Integer> map = new HashMap<>();
    int len = nums.length / 2;
    for (int num : nums) {
        if(!map.containsKey(num))
            map.put(num, 1);
        else {
            if (map.get(num)==len)
                return num;
            map.put(num, map.get(num)+1);
        }
    }

    return 0;
}

排序法

先将数组排序, 然后查看中点的值, 在数组中出现次数超过长度一半的话, 那么中位数一定是这个数.

代码不再贴出

摩尔投票法

核心理念为 “正负抵消” ；时间和空间复杂度分别为 O(N)O(N) 和 O(1)O(1) ；是本题的最佳解法。

票数和 由于众数出现的次数超过数组长度的一半；若记众数的票数为 +1+1 ，非众数 的票数为 -1−1 ，则一定有所有数字的 票数和 > 0>0 。
票数和： 由于众数出现的次数超过数组长度的一半；若记众数的票数为 +1，非众数 的票数为 -1 ，则一定有所有数字的 票数和 > 0 。

算法原理:

先假设第一个元素为众数, 票数是1, 往后遍历, 一旦遇到相同的数就+1, 遇到不同的数就-1, 如果票数为0了, 换下一个元素当众数, 继续投票

也就是说票数抵消为0了, 就换个数继续遍历, 最后结束遍历的时候当前的数绝对就是众数

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