简述网站制作过程,网站建设自建与租用区别,wordpress+绿色,广东官网网站建设平台【LetMeFly】2251.花期内花的数目#xff1a;排序 二分
力扣题目链接#xff1a;https://leetcode.cn/problems/number-of-flowers-in-full-bloom/
给你一个下标从 0 开始的二维整数数组 flowers #xff0c;其中 flowers[i] [starti, endi] 表示第 i 朵花的 花期 从 st…【LetMeFly】2251.花期内花的数目排序 二分
力扣题目链接https://leetcode.cn/problems/number-of-flowers-in-full-bloom/
给你一个下标从 0 开始的二维整数数组 flowers 其中 flowers[i] [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi 都 包含。同时给你一个下标从 0 开始大小为 n 的整数数组 persons persons[i] 是第 i 个人来看花的时间。
请你返回一个大小为 n 的整数数组 answer 其中 answer[i]是第 i 个人到达时在花期内花的 数目 。 示例 1 输入flowers [[1,6],[3,7],[9,12],[4,13]], persons [2,3,7,11]
输出[1,2,2,2]
解释上图展示了每朵花的花期时间和每个人的到达时间。
对每个人我们返回他们到达时在花期内花的数目。示例 2 输入flowers [[1,10],[3,3]], persons [3,3,2]
输出[2,2,1]
解释上图展示了每朵花的花期时间和每个人的到达时间。
对每个人我们返回他们到达时在花期内花的数目。提示
1 flowers.length 5 * 104flowers[i].length 21 starti endi 1091 persons.length 5 * 1041 persons[i] 109
方法一排序 二分
将所有的开花时间放入一个数组并从小到大排序将所有的闭花时间也放入一个数组并从小到大排序。
对于某个时刻某一天当前盛开的花朵的数量为 开花时间小于等于当前时间的花数 − 闭花小于等于当前时间前一天的花数 开花时间小于等于当前时间的花数 - 闭花小于等于当前时间前一天的花数 开花时间小于等于当前时间的花数−闭花小于等于当前时间前一天的花数。
如何快速得到非降序数组 a a a中 ≤ k \leq k ≤k的元素的个数二分即可。C的upper_bound / Python的bisect_right
时间复杂度 O ( ( n m ) log n ) O((n m)\log n) O((nm)logn)其中 n l e n ( f l o w e r s ) n len(flowers) nlen(flowers) m l e n ( p e o p l e ) m len(people) mlen(people)空间复杂度 O ( n ) O(n) O(n)力扣返回值不计入算法空间复杂度
AC代码
C
class Solution {
public:vectorint fullBloomFlowers(vectorvectorint flowers, vectorint people) {vectorint start(flowers.size()), end(flowers.size()), ans(people.size());for (int i 0; i flowers.size(); i) {start[i] flowers[i][0];end[i] flowers[i][1];}sort(start.begin(), start.end());sort(end.begin(), end.end());for (int i 0; i people.size(); i) {// 到这一天为止的开花总数 - 到这一天的前一天为止的闭花总数int hanagasaku upper_bound(start.begin(), start.end(), people[i]) - start.begin(); // 花が咲く(はながさく)int hanagatiru upper_bound(end.begin(), end.end(), people[i] - 1) - end.begin();// 花が散る(はながちる)ans[i] hanagasaku - hanagatiru;}return ans;}
};Python
真简
# from typing import List
# from bisect import bisect_rightclass Solution:def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) - List[int]:start sorted([f[0] for f in flowers])end sorted([f[1] for f in flowers])return [bisect_right(start, p) - bisect_right(end, p - 1) for p in people] 同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/133378624
