Leetcode 455 分发饼干

题意理解：

? ? ? ? 小孩的饭量：?[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()

空间复杂度：O()

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

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

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

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