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

LeetCode 2251 花期内花的数目 C 语言实现思路把所有花的开始时间、结束时间分别拆成两个数组对两个数组排序对每个人的到达时刻t开花数开始时间 ≤ t的花数量凋谢数结束时间 t的花数量答案 开花数 - 凋谢数手写二分上界、下界C 完整可提交代码#includestdlib.h// 快速排序比较函数staticintcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}// 二分找 target 的元素个数 (upper_bound)staticintupper_bound(int*arr,intn,inttarget){intl0,rn;while(lr){intmidl(r-l)/2;if(arr[mid]target)lmid1;elsermid;}returnl;}// 二分找 target 的元素个数 (lower_bound)staticintlower_bound(int*arr,intn,inttarget){intl0,rn;while(lr){intmidl(r-l)/2;if(arr[mid]target)lmid1;elsermid;}returnl;}/** * Note: The returned array must be malloced, assume caller calls free(). */int*fullBloomFlowers(int**flowers,intflowersSize,int*flowersColSize,int*people,intpeopleSize,int*returnSize){*returnSizepeopleSize;int*start(int*)malloc(sizeof(int)*flowersSize);int*end(int*)malloc(sizeof(int)*flowersSize);// 拆分起止时间for(inti0;iflowersSize;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(inti0;ipeopleSize;i){inttpeople[i];intbloomupper_bound(start,flowersSize,t);intfadelower_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动态分配符合题目要求「返回数组需动态申请」。