每日一题:LeetCode:1996.游戏中弱角色的数量

浏览次数 : 次 2022-01-28

博文字数统计 : 1.2k字 | 阅读所需时长 : 4分

× 文章目录

1. 2022-01-28：LeetCode：1996.游戏中弱角色的数量

每日一题：LeetCode：1996.游戏中弱角色的数量
- 时间：2022-01-28
- 力扣难度：Medium
- 个人难度：Medium
- 数据结构：数组
- 算法：排序、单调栈

2022-01-28：LeetCode：1996.游戏中弱角色的数量

1. 题目描述

题目：原题链接
- 你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击和防御。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。
- 如果存在一个其他角色的攻击和防御等级都严格高于该角色的攻击和防御等级，则认为该角色为弱角色。
- 更正式地，如果认为角色 i 弱于存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。
- 返回弱角色的数量。
- 2 <= properties.length <= 10^5
- properties[i].length == 2
- 1 <= attacki, defensei <= 10^5
输入输出规范
- 输入：二维数组，表示角色属性
- 输出：弱角色个数
输入输出示例
- 输入：properties = [[1,5],[10,4],[4,3]]
- 输出：1

2. 方法一：排序

思路
- 本题中，弱角色的定义是攻击、防御都小于另一个角色，因此可以先对二维数组按照攻击进行降序排列
- 排序之后，对数组进行遍历，对于遍历到的当前元素，只要存在前面的元素的防御力比当前元素的大，就找到一个弱角色
- 具体而言，为了判断前面的元素的防御力是否大于当前元素，我们可以维护一个变量，表示当前遍历过的元素中的最大防御值，只要当前元素防御值小于该最大值，就是弱元素
- 此外，本题的数据中存在攻击力相等的元素，此时对于任意一个元素，如果最大防御值大于该元素的防御值，但是两者的攻击力相同，那么该元素就不是弱元素
- 对于这一情况，我们可以定制数组排序的规则，当攻击力相同时，按照防御力升序排列
- 这样做可以使得当遍历到同一个攻击力的多个元素时，先遍历到防御力小的元素并判断其是不是弱元素
- 如果是弱元素，最大防御值不会改变，后续遍历到的同攻击力的元素所对比的最大防御值是高攻击力的元素

题解

public int numberOfWeakCharacters(int[][] properties) {
       Arrays.sort(properties, (o1, o2) -> {
           return o1[0] == o2[0] ? (o1[1] - o2[1]) : (o2[0] - o1[0]);
       });
       int maxDefense = 0;
       int count = 0;
       for (int[] property : properties) {
           if (property[1] < maxDefense) {
               count++;
           } else {
               maxDefense = property[1];
           }
       }
       return count;
   }

复杂度分析：n 是二维数组的长度
- 时间复杂度：$O(nlogn)$
- 空间复杂度：$O(logn)$

3. 方法二：桶思想

思路
- 使用排序API来完成本题的时间复杂度是线性对数级，那么是否可以优化到线性复杂度呢
- 其实如果不存在相同攻击力、防御力的元素，那么可以通过一次遍历求得最大攻击力和最大防御力，然后再遍历一次数组判断当前元素是否小于两个最大值即可，是线性的复杂度
- 那么，相当于只是多了存在相同攻击力、防御力的元素的情况，此时可以通过桶的思想维护一个辅助数组bucket **，用来存储每个大于该攻击力的元素中对应的最大防御力，可以成为局部最大防御力**
- 然后，同样是遍历数组，判断当前元素是否小于最大攻击力，且小于当前元素攻击力对应的 bucket 数组中保存的局部最大防御力

题解

public int numberOfWeakCharacters(int[][] properties) {
    // 求最大攻击力
    int maxAttack = 0;
    for (int[] property : properties) {
        maxAttack = Math.max(maxAttack, property[0]);
    }

    // bucket数组，先存储每个攻击力对应的最大防御力
    int[] bucket = new int[maxAttack + 1];
    for (int[] property : properties) {
        bucket[property[0]] = Math.max(bucket[property[0]], property[1]);
    }

    // bucket数组，存储大于当前攻击力的元素的最大防御力
    int maxDefence = 0; // 已遍历过的元素中的最大防御力
    for (int i = maxAttack; i >= 0; i--) {
        int prev = maxDefence;
        maxDefence = Math.max(maxDefence, bucket[i]);
        bucket[i] = prev;
    }

    int count = 0;
    // 遍历寻找弱角色
    // 小于最大攻击力，小于比当前元素攻击力大的元素的最大防御力
    for (int[] property : properties) {
        if (property[0] < maxAttack && property[1] < bucket[property[0]]) {
            count++;
        }
    }
    return count;
}

复杂度分析：n 是二维数组的长度
- 时间复杂度：$O(n+C)$，C 是最大的攻击力
- 空间复杂度：$O(C)$

本文作者： Chthollists
发布时间： 2022-01-28 22:13:59
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1996.游戏中弱角色的数量
本文链接： https://chthollists.github.io/post/5f60956b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！