豆包 LeetCode 2251. 花期内花的数目 C实现

LeetCode 2251 花期内花的数目 C 语言实现

思路

1. 把所有花的开始时间、结束时间分别拆成两个数组
2. 对两个数组排序
3. 对每个人的到达时刻t：
   • 开花数：开始时间 ≤ t的花数量
   • 凋谢数：结束时间 < t的花数量
   • 答案 = 开花数 - 凋谢数
4. 手写二分：上界、下界

C 完整可提交代码

#include<stdlib.h>// 快速排序比较函数staticintcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}// 二分：找 <= target 的元素个数 (upper_bound)staticintupper_bound(int*arr,intn,inttarget){intl=0,r=n;while(l<r){intmid=l+(r-l)/2;if(arr[mid]<=target)l=mid+1;elser=mid;}returnl;}// 二分：找 < target 的元素个数 (lower_bound)staticintlower_bound(int*arr,intn,inttarget){intl=0,r=n;while(l<r){intmid=l+(r-l)/2;if(arr[mid]<target)l=mid+1;elser=mid;}returnl;}/** * Note: The returned array must be malloced, assume caller calls free(). */int*fullBloomFlowers(int**flowers,intflowersSize,int*flowersColSize,int*people,intpeopleSize,int*returnSize){*returnSize=peopleSize;int*start=(int*)malloc(sizeof(int)*flowersSize);int*end=(int*)malloc(sizeof(int)*flowersSize);// 拆分起止时间for(inti=0;i<flowersSize;i++){start[i]=flowers[i][0];end[i]=flowers[i][1];}// 排序qsort(start,flowersSize,sizeof(int),cmp);qsort(end,flowersSize,sizeof(int),cmp);int*ans=(int*)malloc(sizeof(int)*peopleSize);for(inti=0;i<peopleSize;i++){intt=people[i];intbloom=upper_bound(start,flowersSize,t);intfade=lower_bound(end,flowersSize,t);ans[i]=bloom-fade;}free(start);free(end);returnans;}

核心原理

• 一朵花[s, e]：s 当天开，e 当天仍然开
• 所以凋谢条件是：结束时间 < t
• 用两次二分相减直接得到当前盛开数量

复杂度

• 排序：(O(n\log n))
• 每个人二分：(O(m\log n))
• 整体：(O(n\log n + m\log n))，最优时间复杂度

使用说明

LeetCode C 模板直接粘贴即可通过；
数组都是malloc动态分配，符合题目要求「返回数组需动态申请」。