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

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

一、题目描述

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;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/790899.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表(0条)

保存