Leetcode 1996. 游戏中若角色的数量

Leetcode 1996. 游戏中若角色的数量

题目

https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game/

分析

题目要求将弱角色的数目统计出来,自己使用\(O(n^2)\)的办法做的,最后肯定超时了,看了一下题解才明白\(O(n)\)直接就能做出来,这里排除了排序,算上排序是\(O(nlogn)\)

办法就是将角色的攻击力升序排列,对于攻击力相同的角色按照防御力降序排列。

1 5 
1 5
1 2
3 10
4 3
7 7
7 3
8 10
9 8
9 7

排完顺序的一个样例如上,这样,我们从尾部开始遍历,比较防御力低于当前防御力max的角色,如果低于即更新count。由于排序特点,在攻击力相同时当前防御力一定是大于防御力max的,只需要比较防御力即可,一次遍历即可统计出弱角色数量。

solution

class Solution {
    public int numberOfWeakCharacters(int[][] property) {
        Arrays.sort(property, (o1, o2) -> (o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]));
        int count = 0;
        int maxDefend = -1;
        for (int i = property.length - 1; i >= 0; i--) {
            if (maxDefend > property[i][1]) {
                count++;
                continue;
            }
            maxDefend = Math.max(maxDefend, property[i][1]);
        }
        return count;
    }
}

做题还是要耐心的,自己在超时后直接打开了题解,发现和自己的做法差不多,再分析优化一下感觉单独还是能做出来的。。。

上一篇:全方位揭秘阿里云企业应用中心


下一篇:【LOJ6033】「雅礼集训 2017 Day2」棋盘游戏(二分图博弈)