题目

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

思路1(排序)

  • 因为题目说一定会存在超过数组长度一半的一个数字,所以我们将数组排序后,位于length/2位置的一定是众数

代码

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

复杂度分析

  • 时间复杂度:\(O(NlogN)\)
  • 空间复杂度:\(O(1)\)

思路2(哈希表)

  • 遍历一遍数组,将数组的值作为键,出现的次数作为值,存放到哈希表中
  • 遍历哈希表,找到出现次数最多的那一个键值对就是我们要的众数

代码

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        int max = 0;
        int res = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (max < entry.getValue()) {
                max = entry.getValue();
                res = entry.getKey();
            }
        }
        return res;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(N)\)

思路3(分治)

  • 将数组从中间开始不断分成两份,直到只剩下一个元素时候开始返回
  • 如果left和right出现的频率一样,直接返回
  • 计算left和right在lo~hi范围内出现的频率,将高频率的返回
  • 为什么可以用这个方法?比如有[1, 2, 3, 2, 2, 2, 5, 4, 2],共有9个元素,共会被分成5份(每份一个或者两个元素),然后从每份中再获取一个值,共获取5个值,又因为众数的个数要大于数组的长度,所以,众数一定会至少被选中一个,只要被选中一个,那么我们的countInRange函数会根据范围帮我们计算出最多出现的元素个数即众数

代码

class Solution {
    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length-1);
    }

    public int majorityElementRec(int[] nums, int lo, int hi) {
        // 如果只有一个元素,那么直接返回
        if (lo == hi) {
            return nums[lo];
        }

        // 获取中间值
        int mid = lo + (hi - lo) / 2;
        // 递归左边和右边,直到剩下一个元素
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid+1, hi);

        // 相等只需要返回一个
        if (left == right) {
            return left;
        }

        // 计算left和right在lo~hi范围中的出现的次数
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        // 返回出现次数多的数
        return leftCount > rightCount ? left : right;
    }

    // 统计目标数字在指定范围出现的次数
    public int countInRange(int[] nums, int target, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == target) {
                count++;
            }
        }
        return count;
    }
}

复杂度分析

  • 时间复杂度:\(O(NlogN)\)
  • 空间复杂度:\(O(logN)\),递归过程中使用了额外的栈空间

思路4(摩尔投票法)

  • 众数记为+1,把其他数记为-1,将它们全部加起来,和最终会大于0
  • 假设众数记为res,票数记为votes,假设有这么一个数组:[1, 2, 3, 2, 2, 2, 5, 4, 2],使用摩尔投票法的过程如下:
    • i=0时:因为当前票数为0,所以将1赋值给res,同时票数也加一。此时res=1 votes=1
    • i=1时:2不等于1,所以票数要减1,此时res=1 votes=0
    • i=2时:因为票数为0,所以众数res要指向当前的3,然后票数加一,此时res=3 votes=1
    • i=3时:2不等于3,所以票数要减1,此时res=3 votes=0
    • i=4时:因为票数为0,所以众数res要指向当前的2,然后票数加一,此时res=2 votes=1
    • i=5时:由于2=2,所以票数加一,此时res=2 votes=2
    • i=6时:5不等于2,所以票数要减1,此时res=2 votes=1
    • i=7时:4不等于2,所以票数要减1,此时res=2 votes=0
    • i=8时:因为票数为0,所以众数res要指向当前的2,然后票数加一,此时res=2 votes=1
    • 最后就直接输出res即为众数

代码

class Solution {
    public int majorityElement(int[] nums) {
        // 代表结果的众数
        int res = nums[0];
        // 统计票数
        int votes = 0;

        for (int i = 0; i < nums.length; i++) {
            // 刚开始是0票,所以把数组的第一个元素作为众数
            // 如果以后的循环votes票数被抵消掉了为0,那么下一个元素就作为众数
            if (votes == 0) {
                res = nums[i];
            }
            // 和当前众数相同的,那么票数就加1
            if (res == nums[i]) {
                votes++;
            } else {
                // 如果和当前票数不同,票数就被抵消掉了一个
                votes--;
            }
        }

        return res;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(1)\)
10-21 14:16