花期内花的数目
难度:
标签:
题目描述
给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间。
请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。
示例 1：
输入：flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11] 输出：[1,2,2,2] 解释：上图展示了每朵花的花期时间，和每个人的到达时间。 对每个人，我们返回他们到达时在花期内花的数目。
示例 2：
输入：flowers = [[1,10],[3,3]], people = [3,3,2] 输出：[2,2,1] 解释：上图展示了每朵花的花期时间，和每个人的到达时间。 对每个人，我们返回他们到达时在花期内花的数目。
提示：
1 <= flowers.length <= 5 * 104flowers[i].length == 21 <= starti <= endi <= 1091 <= people.length <= 5 * 1041 <= people[i] <= 109
代码结果
运行时间: 151 ms, 内存: 39.4 MB
/*
* 思路：
* 使用 Java Stream API 优化计算过程。
* 具体步骤：
* 1. 初始化一个结果数组 answer，大小与 people 数组相同。
* 2. 对于每个到达时间，使用 Stream 过滤和计数花朵的开放时间包含该时间的数量。
* 3. 返回结果数组 answer。
*/
import java.util.Arrays;
public int[] fullBloomFlowers(int[][] flowers, int[] people) {
return Arrays.stream(people)
.map(p -> (int) Arrays.stream(flowers)
.filter(flower -> flower[0] <= p && p <= flower[1])
.count())
.toArray();
}解释
方法:
本题解使用了排序和二分查找的方法来高效地计算每个人到达时在花期内的花的数目。首先，从输入的flowers数组中提取所有花的开始时间和结束时间，并将它们分别排序。使用这两个排序后的数组，可以快速地通过二分查找确定对于任意给定的时间点p，有多少花已经开始开放，以及有多少花已经结束开放。具体地，对于每个人的到达时间p，使用二分查找在开始时间数组中找到第一个大于p的位置（start_idx），这表示直到时间p为止已经开始开放的花的数量；在结束时间数组中找到第一个大于或等于p的位置（end_idx），这表示直到时间p刚好还没有结束开放的花的数量。花期内的花的数量即为 start_idx - end_idx。
时间复杂度:
O(n log n + m log n)
空间复杂度:
O(n + m)
代码细节讲解
🦆
二分查找返回的`start_idx`和`end_idx`如何准确反映在p时刻正在开放的花的数量，能否详细解释这两个索引的计算逻辑？
▷