【LetMeFly】2251.花期內(nèi)花的數(shù)目：排序 + 二分

力扣題目鏈接：https://leetcode.cn/problems/number-of-flowers-in-full-bloom/

給你一個下標(biāo)從 0?開始的二維整數(shù)數(shù)組?flowers?，其中?flowers[i] = [starti, endi]?表示第?i?朵花的 花期?從?starti?到?endi?（都 包含）。同時給你一個下標(biāo)從 0?開始大小為 n?的整數(shù)數(shù)組?persons?，persons[i]?是第?i?個人來看花的時間。

請你返回一個大小為 n?的整數(shù)數(shù)組?answer?，其中?answer[i]是第?i?個人到達(dá)時在花期內(nèi)花的?數(shù)目?。

?

示例 1：

輸入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
輸出：[1,2,2,2]
解釋：上圖展示了每朵花的花期時間，和每個人的到達(dá)時間。
對每個人，我們返回他們到達(dá)時在花期內(nèi)花的數(shù)目。

示例 2：

輸入：flowers = [[1,10],[3,3]], persons = [3,3,2]
輸出：[2,2,1]
解釋：上圖展示了每朵花的花期時間，和每個人的到達(dá)時間。
對每個人，我們返回他們到達(dá)時在花期內(nèi)花的數(shù)目。

?

提示：

• 1 <= flowers.length <= 5 * 104
• flowers[i].length == 2
• 1 <= starti <= endi <= 109
• 1 <= persons.length <= 5 * 104
• 1 <= persons[i] <= 109

方法一：排序 + 二分

將所有的開花時間放入一個數(shù)組并從小到大排序；將所有的閉花時間也放入一個數(shù)組并從小到大排序。

對于某個時刻（某一天），當(dāng)前盛開的花朵的數(shù)量為：$開花時間小于等于當(dāng)前時間的花數(shù)?閉花小于等于當(dāng)前時間前一天的花數(shù)$。

如何快速得到非降序數(shù)組$a$中$\le k$的元素的個數(shù)？二分即可。（C++的upper_bound / Python的bisect_right）

• 時間復(fù)雜度$O((n+m)\log n)$，其中$n=len(flowers)$，$m=len(people)$
• 空間復(fù)雜度$O(n)$，力扣返回值不計(jì)入算法空間復(fù)雜度

AC代碼

C++

class Solution {
public:vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {vector<int> 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++) {// 到這一天為止的開花總數(shù) - 到這一天的前一天為止的閉花總數(shù)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]

同步發(fā)文于CSDN，原創(chuàng)不易，轉(zhuǎn)載經(jīng)作者同意后請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133378624