当前位置：首页 > article >正文

【代码随想录】LC 455. 分发饼干

article 2025/3/19 14:24:11

文章目录

前言
一、题目
- 1、原题链接
- 2、题目描述
二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解

前言

本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记，如有侵权，立即删除。

一、题目

1、原题链接

455. 分发饼干

2、题目描述

二、解题报告

1、思路分析

（1）根据贪心的思路，由于大饼干可以满足胃口大的孩子，也能满足胃口小的孩子，我们为了能够让更多的孩子得到满足，我们可以优先将大的饼干先满足胃口大的孩子，然后以此类推，将次小的饼干满足胃口次小的孩子…
（2）所以我们可以先将每个孩子的胃口值和每个饼干的尺寸进行排序。然后从胃口大的孩子开始枚举，同样用尺寸大的饼干开始枚举，判断该饼干能否满足该孩子，若能则记录的答案数加一，同时枚举下一个孩子和下一个饼干；若不能满足，枚举下一个孩子，还是上次枚举的饼干，看是否能满足，以此类推。（注：在枚举过程中，由于胃口数组和饼干数组可能长度不一致以及每次枚举时元素是否需要变化等问题，同时注意数组的边界问题）

2、时间复杂度

时间复杂度O(nlogn)

3、代码详解

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int ans = 0;    //记录答案
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int j = s.size() - 1;    //饼干数组指针，初始指向最大尺寸饼干下标，也就是最后一个元素下标
        //从后往前枚举孩子
        for (int i = g.size() - 1; i >= 0; i--) {
            //注意条件，j>=0要首先判断，否则会出现数组下标越界，出现错误
            if (j >= 0 && g[i] <= s[j] ) {  //若s[j]饼干可以满足g[i]孩子则答案+1、饼干数组指针前移
                ans++;
                j--;
            }
        }
        return ans;
    }
};