Leetcode 455 分发饼干

2023-12-15 20:38:12

题意理解

? ? ? ? 小孩的饭量:?[1,2,7,10]

? ? ? ? 饼的大小:?????[1,3,5,7]

? ? ? ? 当饼的大小>=小孩饭量时,小孩就能够吃饱。

? ? ? ? 求如何分配饼让更多的小孩子能够吃饱。

解题思路

? ? ? ? 两种思路:

? ? ? ? 先把胃口小的孩子用较小的饼来喂饱——保证更多的小孩能吃饱

? ? ? ? 先把大饼为给胃口较大且能吃饱的孩子——保证更多的小孩能吃饱

? ? ? ? 局部最优——每个饼,给刚好能吃饱又不会剩太多的孩子——【全局最优】更多小孩能吃饱

1.贪心解题

小饼给小孩

   public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int result=0;
        int g_index=0;
        //小饼给小孩-遍历饼
        for(int i=0;i<s.length;i++){
            while(g_index<g.length&&g[g_index]<=s[i]){
                result++;
                g_index++;
                break;
            }
        }
        return result;
    }

大饼给大孩

public int findContentChildren2(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int result=0;
        int s_index=s.length-1;
        //大饼给大孩-遍历孩
        for(int i=g.length-1;i>=0;i--){
            if(s_index>=0&&g[i]<=s[s_index]){
                result++;
                s_index--;
            }
        }
        return result;
    }

2.分析

时间复杂度:O(m+n+log(m)+log(n))

空间复杂度:O(log(m)+log(n))

排序的时间复杂度:O(log(n))

遍历的时间复杂度:O(n)

排序的额外空间开销:O(log(n))

两个数组的长度分别为m,n

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135023891
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。