455. 分配饼干
小白解法
class Solution { public: int findContentChildren(vector<int> &g, vector<int> &s) { int count = 0; sort(g.begin(), g.end()); sort(s.begin(), s.end()); for (int i = 0; i < s.size(); i++) { for (int j = 0; j < g.size(); j++) { if (s[i] >= g[j]) { count++; g.erase(g.begin() + j); 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 count = 0; int child = 0, cookie = 0; while (child < g.size() && cookie < s.size()) { if (g[child] <= s[cookie]) { child++; } cookie++; } return child; } };
胃口小的孩子最容易饱，所以2先考虑这个孩子。把大于等于这个孩子胃口的大小最小的饼干给这个孩子。采用同样策略，考虑剩下的孩子，直到没有满足条件的饼干存在。
