leetcode
leetcode 1751 ~ 1800
游戏中弱角色的数量

游戏中弱角色的数量

难度:

标签:

题目描述

代码结果

运行时间: 386 ms, 内存: 52.9 MB


// Java Stream Solution
// 题目思路:
// 同样的思路,使用 Java Stream 来实现。
// 首先按攻击值从高到低排序,如果攻击值相同则按防御值从低到高排序。
// 使用 Stream API 处理数组,获取弱角色的数量。

import java.util.Arrays;

public class WeakCharactersStream {
    public int numberOfWeakCharacters(int[][] properties) {
        int[] maxDefense = {0};
        return (int) Arrays.stream(properties)
            .sorted((a, b) -> b[0] == a[0] ? a[1] - b[1] : b[0] - a[0])
            .filter(property -> {
                boolean isWeak = property[1] < maxDefense[0];
                if (!isWeak) maxDefense[0] = property[1];
                return isWeak;
            }).count();
    }
}

解释

方法:

题解的核心思路是通过排序和一次遍历来确定弱角色的数量。首先,我们将角色按照攻击力进行降序排序,如果攻击力相同,则按照防御力升序排序。这样做的目的是:当我们在遍历列表时,每次遇到的角色,其后面的角色攻击力要么相同要么更小。因此,我们只需要关心防御力的比较。在遍历过程中,我们维护一个记录之前角色最大防御力的变量max_defense。对于每个角色,如果其防御力小于max_defense,则它是一个弱角色。这样,我们可以在单次遍历中完成弱角色的计数。

时间复杂度:

O(n log n)

空间复杂度:

O(log n)

代码细节讲解

🦆
为什么在排序时选择先按攻击力降序,再按防御力升序,而不是两者都按降序或升序排序?
按攻击力降序排序确保在遍历时,每个角色都不会遇到攻击力更高的角色,因此我们只需比较防御力。而防御力升序排序防止攻击力相同的角色中防御力较高的角色被错误地认定为弱角色。如果两者都按降序排序,防御力高的角色可能排在防御力低的角色之后,导致高防御力角色被错误地认为是弱角色。
🦆
在遍历角色属性列表时,若当前角色的攻击力相同,防御力更高,是否会被错误地认为是弱角色?
不会。由于防御力是按升序排序的,当攻击力相同时,防御力较低的角色会先被处理,其防御力不会被认为是最大防御力。因此,随后遇到的防御力较高的角色不会被认为弱角色,因为其防御力会大于或等于之前角色的防御力。
🦆
在更新max_defense变量时,为什么只在当前角色的防御力大于max_defense时才更新它,而不是每次都更新?
因为我们只需要知道历史上遇到的最强的防御力来确定当前角色是否为弱角色。如果当前角色的防御力不高于max_defense,则该角色为弱角色,但这并不影响max_defense的值。只有当遇到更高的防御力时,才需要更新max_defense,以确保正确地评估后续角色。
🦆
如果properties数组为空或只包含一个角色,这个算法是否还有效?
是的,算法仍然有效。如果数组为空,排序不会改变数组,遍历开始时就会结束,返回的弱角色数为0。如果数组只包含一个角色,由于没有其他角色可以比较,该角色也不会被认为是弱角色,结果同样是0。

相关问题