Assign Cookies
每个孩子 i 都有一个贪心因子 g[i]，表示能让他们开心的最小饼干尺寸。每块饼干 j 都有一个尺寸 s[j]。当孩子得到一块尺寸至少达到其贪心因子的饼干时，就会满足。每个孩子最多得到一块饼干，每块饼干最多分给一个孩子。返回你最多能让多少个孩子满足。
函数
- ginteger-array
- 每个孩子的贪心因子，他们接受的最小饼干尺寸
- sinteger-array
- 每块饼干的大小
- 返回值integer
- 最多能让多少个孩子各自拿到一个大小至少等于其贪心因子的饼干
约束条件
1 ≤ g.length, s.length ≤ 50001 ≤ g[i], s[j] ≤ 105- 这两个数组的长度可能不同，而且都没有排序。
示例
- 输入
- g = [4, 2, 7]s = [3, 5, 1, 2]
- 输出
- 2
- 解释
- 排序后，孩子们想要 2、4 和 7。饼干 2 分给想要 2 的孩子，饼干 5 分给想要 4 的孩子。没有饼干能满足想要 7 的孩子，所以答案是 2。
- 输入
- g = [3, 3, 3]s = [2, 2, 2]
- 输出
- 0
- 解释
- 每个孩子都想要一个大小至少为 3 的饼干，而每块饼干的大小都是 2，所以没有孩子能得到满足。
进阶
如果每个孩子也都有自己能接受的最大尺寸，那么每块饼干只有在一定范围内才符合要求。这时，每块饼干应该分给哪个等待的孩子呢？
提示
逐个打开提示，每个都会多透露一点。
哪个孩子最容易满足？哪块饼干价格最低，但仍能让他们满意？
用能满足孩子需求的最小饼干来喂孩子不会有坏处：你省下的任何更大的饼干，都可以用来喂同样的孩子。因此，按饼干从小到大的顺序分发，先满足需求最少的孩子。
将两个数组都排序。从最小的饼干开始依次查看，并用一个指针指向仍在等待、贪心程度最低的孩子。如果饼干足够大，能满足这个孩子的需求，就让孩子吃到饼干，然后将指针移到下一个孩子；否则，这块饼干对所有等待的孩子来说都太小了，就跳过它。指针的最终位置就是答案。
题解
尝试所有儿童和饼干的配对会让情况变得复杂，但一条贪心规则就能解决问题：先满足胃口最小的儿童，给他们能满足需求的最小饼干。将两个数组排序后，这条规则就变成了用两个指针遍历一次。
为每个孩子分配最小的合适饼干
结果正确，但无法在最大的测试中运行完毕
思路
按贪心程度从低到高处理孩子，并给每个孩子分配最小的、尚未使用且足够大的饼干。更大的饼干能满足所有能被较小饼干满足的孩子，因此分配刚好够用的最小饼干，就能把更大的饼干留给之后贪心程度更高的孩子。
每个 n 个孩子都会扫描所有 m 块饼干：当 n = m = 5000 时，总共要检查 2500 万次。
算法
- 将贪心因子从小到大排序。
- 为每块饼干设置一个标记，表示它是否已被使用。
- 对于每个孩子，扫描所有饼干，并记下其中尺寸不小于该孩子贪心因子的最小未使用饼干。
- 如果找到了，就将它标记为已使用，并将该孩子计为满足。
- 返回计数。
def findContentChildren(g, s):
used = [False] * len(s)
fed = 0
for need in sorted(g): # least greedy child first
best = -1
for j in range(len(s)):
if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
best = j
if best != -1:
used[best] = True
fed += 1
return fed对两者排序并使用双指针
思路
也要对饼干排序，这样就能先遇到最小的合适饼干。用一个指针 child，指向仍在等待的孩子中胃口最小的那个，从小到大逐个查看饼干。如果饼干大小至少为 g[child]，就把饼干分给这个孩子，然后移动指针。更小的饼干也小于所有等待孩子的胃口，因此没有用处。
在第一个示例中，饼干 1 对胃口为 2 的孩子来说太小，饼干 2 分给了想要 2 的孩子，饼干 3 对胃口为 4 的孩子来说太小，饼干 5 分给了想要 4 的孩子。指针停在 2。
每个指针都只向前移动，因此遍历的复杂度是 O(n + m)，主要耗时来自两次排序。
算法
- 按升序对
g和s排序。 - 设置
child = 0，表示仍在等待的贪心程度最低的孩子。 - 从最小的饼干开始依次处理：如果
child仍在g的范围内，且饼干的大小至少为g[child]，就将child加 1。 - 返回
child，即吃到饼干的孩子数量。
def findContentChildren(g, s):
g.sort()
s.sort()
child = 0 # the least greedy child still waiting
for size in s: # smallest cookie first
if child < len(g) and size >= g[child]:
child += 1
return child
易错点和边界情况
- 给孩子的饼干比他们需要的更大。例如，
g = [1, 2]且s = [1, 3]时，把 3 号饼干给想要 1 的孩子，会让想要 2 的孩子挨饿。 - 饼干太小时移动孩子指针。孩子仍然需要饼干，没用的是这块饼干。
- 跳过孩子指针的边界检查。例如，
g = [1]且s = [1, 2]时，读取饼干 2 会越过g的末尾。 - 使用
>而不是≥进行比较。饼干的大小刚好等于贪心因子就够了。 - 把数字当作文本排序。在 JavaScript 中，不带比较器的
sort()会把 10 排在 9 前面。
常见问题3
Assign Cookies 的时间复杂度是多少？
对两个数组进行排序的开销为 O(n log n + m log m)，之后使用双指针遍历的开销为 O(n + m)，因此排序占主导。原地排序可将额外空间保持在 O(1)，不包括排序本身使用的空间。
为什么贪心选择适用于分配饼干？
设 k 是能满足最不贪心的孩子的最小饼干，并假设某个最优分配方案给了这个孩子另一块饼干。交换一下：这个孩子拿 k，原来拿着 k 的人拿另一块饼干。另一块饼干至少一样大，因此两个人都能吃饱。数量不会改变，对剩下的人重复这个论证即可。
你可以改为从最贪心的孩子开始吗？
是的。对两个数组排序，然后从最大的饼干和最贪心的孩子开始遍历。如果剩下最大的饼干能满足剩下最贪心的孩子，就把饼干给他，并移动两个指针；如果不能，就没有饼干能满足这个孩子，因此跳过他。这样能在相同时间内得到相同的数量。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findContentChildren(g, s):
# 在这里编写代码测试 #1
测试 #2
参数
g = [4, 2, 7] s = [3, 5, 1, 2]
预期输出
2