游戏中弱角色的数量
难度:
标签:
题目描述
代码结果
运行时间: 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时才更新它,而不是每次都更新?
▷🦆
如果properties数组为空或只包含一个角色,这个算法是否还有效?
▷