【力扣2251】花期内花的数目 JAVA全过程详解

一、题目描述

1. 输入

给你一个下标从 0 开始长度为 m 的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的花期为从 第starti 天到第 endi 天（都包含）。同时给你一个下标从 0 开始长度为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。

2. 输出

请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时能看到花的数目 。

3. 样例

输入：
flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出：
[1,2,2,2]

输入：
flowers = [[1,10],[3,3]], persons = [3,3,2]
输出：
[2,2,1]

二、思路分析

该题难度为困难，既卡时间又卡内存，简单粗暴的数组统计是无法通过的，需要更加巧妙的思路来解决。

假设某游客前来参观，考虑开花时间【不晚于】游客达到时间的花，它们要么(1)正在开放能被游客看到，要么(2)已经凋落无法被看到。而(2)已经凋落的花正是闭花时间【早于】游客到达时间的花，两者数量相减就是游客能看到的花。

由此我们就有了解题的思路：使用两个数组分别存储开花时间startDay和闭花时间endDay，然后使用sort方法对它们各自进行排序；接着用二分法找出startDay <= arriveDay的花数量n、endDay < arriveDay的花数量n2，就能求出游客看到的花数量n1 = n - n2 。

时间复杂度：O( (m+n) logm )
空间复杂度：O( 2m+n )

1. 统计时间、各自排序

for循环遍历flowers数组，用startDay存储开花时间，用endDay存储闭花时间，再分别调用sort()排序

        int[] startDay  = new int[flowers.length];
        int[] endDay    = new int[flowers.length];
        for (int i=0;i<flowers.length;i++)
        {
            startDay[i] = flowers[i][0];
            endDay[i]   = flowers[i][1];
        }
        Arrays.sort(startDay);
        Arrays.sort(endDay);

2. 二分查找

第1步的sort已经保证了2个数组的有序，所以使用二分查找求花的数量。由于“ startDay <= arriveDay”等价于“ startDay < arriveDay+1 ”，这与“ endDay < arriveDay ”形式相同只是参数不用，因此可以统一解决这两个问题。

定义一个函数int lowerNum( int[] arr, int arriveDay )，它的任务是求出arr[]中 < arriveDay的元素个数，那也就等价于求出第一个 >= arriveDay的元素下标。

首先判断arr最后一个元素（最大元素）与arriveDay的大小关系，如果比arriveDay小，那么直接返回arr.length。

然后定义初始左边界left = 0，初始右边界right = arr.length-1。当中间值 < arriveDay时，它显然不是第一个 >= arriveDay的元素，应该在右半部分继续寻找，所以移动左边界、令left = mid+1；当中间值 >= arriveDay时，第一个 >= arriveDay的元素要么在中间值左边、要么就是中间值自己，所以移动右边界、令right = mid。重复上述二分过程直到left与right相遇，就能返回第一个 >= arriveDay的元素下标，也即 < arriveDay的元素个数。

	private int lowerNum(int[] arr, int arriveDay)
    {
        if (arr[arr.length-1]<arriveDay)
            return arr.length;

        int left = 0;
        int right = arr.length-1;

        while (right>left)
        {
            int mid = (left+right)/2;
            if ( arr[mid] < arriveDay )
                left = mid+1;
            else
                right = mid;
        }
        return left;
    }

3. 遍历求解

for循环遍历persons数组，对每个到达时间persons[i]分别计算一次lowerNum( startDay, persons[i]+1 )和lowerNum( endDay, persons[i] )，前者减后者就是该游客能看到的花的数量。

		int[] ret = new int[persons.length];
        for (int i=0;i<persons.length;i++)
            ret[i] = lowerNum(startDay,persons[i]+1)-lowerNum(endDay,persons[i]);
        return ret;

三、完整代码

笔者的完整源代码如下，可以直接提交通过该题。该代码仅供大家参考，如各位大神有更好的想法欢迎留言讨论，期待与您共同进步！

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        int[] startDay  = new int[flowers.length];
        int[] endDay    = new int[flowers.length];
        for (int i=0;i<flowers.length;i++)
        {
            startDay[i] = flowers[i][0];
            endDay[i]   = flowers[i][1];
        }
        Arrays.sort(startDay);
        Arrays.sort(endDay);

        int[] ret = new int[persons.length];
        for (int i=0;i<persons.length;i++)
            ret[i] = lowerNum(startDay,persons[i]+1)-lowerNum(endDay,persons[i]);
        return ret;
    }

    private int lowerNum(int[] arr, int arriveDay)
    {
        if (arr[arr.length-1]<arriveDay)
            return arr.length;

        int left = 0;
        int right = arr.length-1;

        while (right>left)
        {
            int mid = (left+right)/2;
            if ( arr[mid] < arriveDay )
                left = mid+1;
            else
                right = mid;
        }
        return left;
    }
}