LeetCode 455、分发饼干

一、题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干j 分配给孩子i，这个孩子会得到满足。

你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 分发饼干（ LeetCode 455 ）:https://leetcode-cn.com/problems/assign-cookies/
class Solution {
    public int findContentChildren(int[] g, int[] s) {

        // 1、将孩子们的胃口值按照从小到大的顺序排列
        // 优先满足胃口小的孩子
        Arrays.sort(g);

        // 2、将饼干按照从小到大的顺序排列
        Arrays.sort(s);

        // child 代表 g 的下标，即表示有多少孩子的胃口得到满足
        int child = 0;

        // child 代表 s 的下标，即表示目前有多少饼干被使用了
        int cookie = 0;

        // 遍历所有的饼干
        // 遍历过后，饼干只有两种状态
        // 1、要么找到了需要这个饼干的孩子
        // 2、要么剩下的孩子中，胃口值最低的孩子都大于这个饼干的值，那么这个饼干没人要
        while(cookie < s.length && child < g.length){

            // 孩子的胃口得到了满足
            if(s[cookie] >= g[child]){
                // 得到满足的孩子数量加 1
                child++;
            }

            // 查看下一个饼干能否找到需要的孩子
            cookie++;
        }

        // 最后返回孩子数量
        return child;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 分发饼干（ LeetCode 455 ）:https://leetcode-cn.com/problems/assign-cookies/
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 1、将孩子们的胃口值按照从小到大的顺序排列
        // 优先满足胃口小的孩子
        sort(g.begin(), g.end());

        // 2、将饼干按照从小到大的顺序排列
        sort(s.begin(), s.end());

        // child 代表 g 的下标，即表示有多少孩子的胃口得到满足
        int child = 0;

        // child 代表 s 的下标，即表示目前有多少饼干被使用了
        int cookie = 0;

        // 遍历所有的饼干
        // 遍历过后，饼干只有两种状态
        // 1、要么找到了需要这个饼干的孩子
        // 2、要么剩下的孩子中，胃口值最低的孩子都大于这个饼干的值，那么这个饼干没人要
        while(cookie < s.size() && child < g.size()){

            // 孩子的胃口得到了满足
            if(s[cookie] >= g[child]){
                // 得到满足的孩子数量加 1
                child++;
            }

            // 查看下一个饼干能否找到需要的孩子
            cookie++;
        }

        // 最后返回孩子数量
        return child;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 分发饼干（ LeetCode 455 ）:https:#leetcode-cn.com/problems/assign-cookies/
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 1、将孩子们的胃口值按照从小到大的顺序排列
        # 优先满足胃口小的孩子
        g.sort()

        # 2、将饼干按照从小到大的顺序排列
        s.sort()

        # child 代表 g 的下标，即表示有多少孩子的胃口得到满足
        child = 0

        # child 代表 s 的下标，即表示目前有多少饼干被使用了
        cookie = 0

        # 遍历所有的饼干
        # 遍历过后，饼干只有两种状态
        # 1、要么找到了需要这个饼干的孩子
        # 2、要么剩下的孩子中，胃口值最低的孩子都大于这个饼干的值，那么这个饼干没人要
        while cookie < len(s) and child < len(g) :
            # 孩子的胃口得到了满足
            if s[cookie] >= g[child] :
                # 得到满足的孩子数量加 1
                child += 1
            
            # 查看下一个饼干能否找到需要的孩子
            cookie += 1
        
        # 最后返回孩子数量
        return child

复杂度分析

时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是 O(mlogm+nlogn)，遍历数组的时间复杂度是 O(m+n)O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。

空间复杂度：O(logm+logn)，其中 m 和 n 分别是数组 g 和 s 的长度。空间复杂度主要是排序的额外空间开销。