统计作战单位数
难度:
标签:
题目描述
代码结果
运行时间: 50 ms, 内存: 16.3 MB
/*
* 题目思路:
* 1. 使用 Java Stream API 实现类似的功能。
* 2. 我们可以使用 IntStream 的双重流来遍历可能的组合,并进行条件检查。
*/
import java.util.stream.IntStream;
public class Solution {
public int numTeams(int[] rating) {
int n = rating.length;
return (int) IntStream.range(0, n - 2)
.boxed()
.flatMap(i -> IntStream.range(i + 1, n - 1)
.boxed()
.flatMap(j -> IntStream.range(j + 1, n)
.filter(k -> (rating[i] < rating[j] && rating[j] < rating[k]) ||
(rating[i] > rating[j] && rating[j] > rating[k]))
.mapToObj(k -> new int[]{i, j, k})))
.count();
}
}
解释
方法:
题解利用了一种改进的方法,通过排序和二进制索引树(Binary Indexed Tree, BIT 或 Fenwick Tree)来高效计算索引间的关系。首先,它通过将rating数组排序并映射每个值到其排序后的索引,便于后续操作。对每个士兵j,计算在其左侧有多少数小于它(lsmall)和大于它(llarge),同时计算在其右侧有多少数小于它(rsmall)和大于它(rlarge)。这些值可以通过BIT高效地计算。根据题目要求,对于每个j,有效的组合为lsmall * rlarge(形成递增序列)和llarge * rsmall(形成递减序列)。这样,对每个j,计算这两种情况的数量并累加得到最终结果。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在使用二进制索引树(BIT)之前,为什么选择先对评分数组进行排序和映射?这对算法的哪些方面有帮助?
▷🦆
如何确保在使用BIT时,计算的`lsmall`和`llarge`值能够正确反映出每个士兵左侧小于和大于它的士兵数?
▷🦆
对于二进制索引树的`add`和`get_sum`函数,能否详细解释它们如何工作,以及它们是如何通过索引运算实现更新和查询的?
▷