搜索引擎网站入口,网站怎么建设商城,个人养老保险怎么缴纳,鸿铭物流网络建站题意理解#xff1a; 小孩的饭量#xff1a; [1,2,7,10] 饼的大小#xff1a; [1,3,5,7] 当饼的大小小孩饭量时#xff0c;小孩就能够吃饱。 求如何分配饼让更多的小孩子能够吃饱。 解题思路#xff1a; 两种思路#xff1a; 先把胃口小的孩子用较小的饼来喂饱—… 题意理解 小孩的饭量 [1,2,7,10] 饼的大小 [1,3,5,7] 当饼的大小小孩饭量时小孩就能够吃饱。 求如何分配饼让更多的小孩子能够吃饱。 解题思路 两种思路 先把胃口小的孩子用较小的饼来喂饱——保证更多的小孩能吃饱 先把大饼为给胃口较大且能吃饱的孩子——保证更多的小孩能吃饱 局部最优——每个饼给刚好能吃饱又不会剩太多的孩子——【全局最优】更多小孩能吃饱 1.贪心解题
小饼给小孩 public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int result0;int g_index0;//小饼给小孩-遍历饼for(int i0;is.length;i){while(g_indexg.lengthg[g_index]s[i]){result;g_index;break;}}return result;}
大饼给大孩
public int findContentChildren2(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int result0;int s_indexs.length-1;//大饼给大孩-遍历孩for(int ig.length-1;i0;i--){if(s_index0g[i]s[s_index]){result;s_index--;}}return result;}
2.分析 时间复杂度O() 空间复杂度O() 排序的时间复杂度O(log(n)) 遍历的时间复杂度O(n) 排序的额外空间开销O(log(n)) 两个数组的长度分别为m,n
