题目:
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
注意:
你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/assign-cookies
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例:
思路:
贪心算法:保证每次操作都是局部最优的,并且最后得到的结果是全局最优的。
本题中,保证先满足胃口小的孩子,将尽可能小的饼干分给胃口小的孩子,把大的饼干留给胃口大的孩子;
因此,可以先将孩子的胃口和糖果的大小进行排序;
然后,
先满足胃口小的孩子,如果找到满足孩子胃口的糖果,让得到满足的孩子数加一;
如果满足不了,就换下一块大一点的糖果;
直到使用完所有糖果 或者 满足了所有孩子。
代码:
class Solution {
public int findContentChildren(int[] g, int[] s) {
int count = 0;//得到满足的孩子的数量
int pChild = 0;//指向孩子的指针
int pSuger = 0;//指向糖果的指针
Arrays.sort(g);//将孩子的胃口进行排序
Arrays.sort(s);//将糖果的大小进行排序
//直到使用完所有糖果 或者 满足了所有孩子
while (pSuger < s.length && pChild < g.length) {
//先满足胃口小的孩子,如果找到满足孩子胃口的糖果,让得到满足的孩子数加一;
if (s[pSuger] >= g[pChild]) {
count ++;
pChild ++;
}
//如果满足不了,就换下一块大一点的糖果;
pSuger ++;
}
return count;
}
}
时间复杂度:O(n),空间复杂度:O(1)