Leetcode 455. Assign Cookies
2017-10-15 本文已影响0人
岛上痴汉
原题地址: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;
}
};