题目描述(中等难度)

找出数组中数量超过 n/3 的数字,n 是数组的长度。

解法一

题目要求是 O(1) 的空间复杂度,我们先用 map 写一下,看看对题意的理解对不对。

map 的话 key 存数字,value 存数字出现的个数。如果数字出现的次数等于了 n/3 + 1 就把它加到结果中。

public List<Integer> majorityElement(int[] nums) {
    int n = nums.length;
    HashMap<Integer, Integer> map = new HashMap<>();
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        int count = map.getOrDefault(nums[i], 0);
        //之前的数量已经是 n/3, 当前数量就是 n/3 + 1 了
        if (count == n / 3) {
            res.add(nums[i]);
        }
        //可以提前结束
        if (count == 2 * n / 3 || res.size() == 2) {
            return res;
        }
        map.put(nums[i], count + 1);

    }
    return res;
}

解法二

169 题 我们做过找出数组的中超过 n/2 数量的数字,其中介绍了摩尔投票法,这里的话可以改写一下,参考 这里

首先看一下 169 题 我们是怎么做的。

我们假设这样一个场景,在一个游戏中,分了若干个队伍,有一个队伍的人数超过了半数。所有人的战力都相同,不同队伍的两个人遇到就是同归于尽,同一个队伍的人遇到当然互不伤害。

这样经过充分时间的游戏后,最后的结果是确定的,一定是超过半数的那个队伍留在了最后。

而对于这道题,我们只需要利用上边的思想,把数组的每个数都看做队伍编号,然后模拟游戏过程即可。

group 记录当前队伍的人数,count 记录当前队伍剩余的人数。如果当前队伍剩余人数为 0,记录下次遇到的人的所在队伍号。

对于这道题的话,超过 n/3 的队伍可能有两个,首先我们用 group1group2 记录这两个队伍,count1count2 分别记录两个队伍的数量,然后遵循下边的游戏规则。

将数组中的每一个数字看成队伍编号。

group1group2 首先初始化为不可能和当前数字相等的两个数,将这两个队伍看成同盟,它俩不互相伤害。

然后遍历数组中的其他数字,如果遇到的数字属于其中的一个队伍,就将当前队伍的数量加 1

如果某个队伍的数量变成了 0,就把这个队伍编号更新为当前的数字。

否则的话,将两个队伍的数量都减 1

public List<Integer> majorityElement(int[] nums) {
    int n = nums.length;
    long group1 = (long)Integer.MAX_VALUE + 1;
    int count1 = 0;
    long group2 = (long)Integer.MAX_VALUE + 1;
    int count2 = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] == group1) {
            count1++;
        } else if (nums[i] == group2) {
            count2++;
        } else if (count1 == 0) {
            group1 = nums[i];
            count1 = 1;
        } else if (count2 == 0) {
            group2 = nums[i];
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    //计算两个队伍的数量,因为可能只存在一个数字的数量超过了 n/3
    count1 = 0;
    count2 = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] == group1) {
            count1++;
        }
        if (nums[i] == group2) {
            count2++;
        }
    }
    //只保存数量大于 n/3 的队伍
    List<Integer> res = new ArrayList<>();
    if (count1 > n / 3) {
        res.add((int) group1);
    }

    if (count2 > n / 3) {
        res.add((int) group2);
    }
    return res;
}

上边有个技巧就是先将 group 初始化为一个大于 int 最大值的 long 值,这样可以保证后边的 if 条件判断中,数组中一定不会有数字和 group相等,从而进入后边的更新队伍编号的分支中。除了用 long 值,我们还可以用包装对象 Integer,将 group 初始化为 null 可以达到同样的效果。

当然,不用上边的技巧也是可以的,我们可以先在 nums 里找到两个不同的值分别赋值给 group1group2 中即可,只不过代码上不会有上边的简洁。

2020.5.27 更新,@Frankie 提醒,其实不用上边分析的那么麻烦,只需要给 group1group2 随便赋两个不相等的值即可。

因为如果数组中前两个数有和 group1 或者 group2 相等的元素,就进入前两个 if 语句中的某一个,逻辑上也没问题。

如果数组中前两个数没有和 group1 或者 group2 相等的元素,那么就和使用 long 一个性质了。

public List<Integer> majorityElement(int[] nums) {
    int n = nums.length;
    int group1 = 0;
    int count1 = 0;
    int group2 = 1;
    int count2 = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] == group1) {
            count1++;
        } else if (nums[i] == group2) {
            count2++;
        } else if (count1 == 0) {
            group1 = nums[i];
            count1 = 1;
        } else if (count2 == 0) {
            group2 = nums[i];
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    //计算两个队伍的数量,因为可能只存在一个数字的数量超过了 n/3
    count1 = 0;
    count2 = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] == group1) {
            count1++;
        }
        if (nums[i] == group2) {
            count2++;
        }
    }
    //只保存数量大于 n/3 的队伍
    List<Integer> res = new ArrayList<>();
    if (count1 > n / 3) {
        res.add( group1);
    }

    if (count2 > n / 3) {
        res.add(group2);
    }
    return res;
}

解法一算是通用的解法,解法二的话看起来比较容易,但如果只看上边的解析,然后自己写代码的话还是会遇到很多问题的,其中 if 分支的顺序很重要。

results matching ""

    No results matching ""