贪心
解题思路
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的；
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩；
- 将小朋友胃口、饼干大小按照升序序列排序；
- 先喂饱胃口大的小朋友；
复杂度
-
时间复杂度：
O(mlogm + nlogn)，m 和 n 分别是数组 g 和 s 的长度，排序的时间复杂度分别是O(mlogm)、O(nlogn)； -
空间复杂度：
O(1)；
代码实现
var findContentChildren = function (g, s) {
// 1. 将小朋友胃口、饼干大小按照升序序列排序
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let count = 0; // 统计能喂饱几个小朋友
let cookieInx = s.length - 1;
// 2. 先喂饱胃口大的小朋友
for (let i = g.length - 1; i >= 0; i--) {
if (s[cookieInx] >= g[i]) {
cookieInx--;
count++;
}
}
return count;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
css🌰 不规则的文字环绕
上一篇
评论
