Leetcode 455. Assign Cookies

原题地址：https://leetcode.com/problems/assign-cookies/description/

题目描述

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

给小孩分饼干，每个饼干能带来的满足感有高低，小孩的欲望值也有高低，用所给的饼干尽可能多地满足小孩的欲望。

我的思路

给小孩的欲望和饼干的属性值升序排序，然后扫一遍，所以应该就是排序算法的复杂度了。

代码一

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        if(g.size()==0 || s.size()==0){
            return 0;
        }
        int count = 0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int j=0;
        for (int i = 0;i<g.size() && j<s.size();i++){
            for(;j<s.size();){
                if(g[i] <= s[j++]){
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};

代码二

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int res = 0;
        int j = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] >= g[j]){
                res++;
                j++;
                if(j >= g.size()){
                    break;
                }
            }
        }
        return res;
    }
};