leetcode
leetcode 1301 ~ 1350
统计作战单位数

统计作战单位数

难度:

标签:

题目描述

代码结果

运行时间: 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)中以索引的方式高效处理。排序确保了我们可以通过数组索引快速访问任何元素,并在整个数组中维持一致的顺序。映射(即将每个元素的值转换为其在排序数组中的位置)则使得可以使用BIT进行区间和频次查询,而不受原始数据大小和分布的影响。这种方式利用BIT处理数组索引而非值本身,简化了问题复杂度,使得我们可以更加高效地计算小于或大于当前元素的元素数量。
🦆
如何确保在使用BIT时,计算的`lsmall`和`llarge`值能够正确反映出每个士兵左侧小于和大于它的士兵数?
在使用BIT时,通过在遍历每个士兵时更新BIT来确保`lsmall`和`llarge`的正确性。对于每个士兵j,`lsmall`是通过BIT的`get_sum`函数计算其左侧所有小于当前士兵评分的士兵数,实现了通过索引来累加计数。`llarge`则是通过计算到目前为止遍历过的士兵数减去`lsmall`得到的,即到当前士兵为止,总共遍历的士兵数减去小于当前士兵评分的士兵数,就是大于当前士兵评分的士兵数。这种方法确保了在计算每个士兵的`lsmall`和`llarge`时,都能够反映出正确的数量,因为BIT在每次迭代时都被及时更新。
🦆
对于二进制索引树的`add`和`get_sum`函数,能否详细解释它们如何工作,以及它们是如何通过索引运算实现更新和查询的?
二进制索引树(BIT)的`add`函数用于更新树中的值。给定一个索引和一个值,它会将值添加到该索引处,然后向上移动到父节点,直到达到树的顶部。这是通过`x += (-x) & x`实现的,这个操作利用了位运算来快速找到包含当前索引的下一个区间。`get_sum`函数用于查询从数组起始到指定索引的累积和。它从给定索引开始,向下移动到更小的索引,累加这些索引处的值,直至数组开始。这也是通过`x -= (-x) & x`实现的,同样利用位运算快速定位到需要累加的下一个索引。这两个函数的设计使得BIT能够在对数时间复杂度内完成更新和查询操作,非常适合处理频繁更新和需要快速查询的场景。

相关问题