【算法与数据结构】455、LeetCode分发饼干

发布时间:2023年12月18日

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解

一、题目

在这里插入图片描述

二、解法

??思路分析:因为大饼干可以满足大胃口的孩子也必然可以满足小胃口的孩子,如果要尽可能的满足孩子的胃口,那么大饼干就要用来满足大胃口的的孩子。因此先对孩子数组和饼干数组进行排序,然后比大小。这里注意遍历两个数组从数组末端(排序后的最大值)开始比较,遍历的是孩子数组。如果满足if语句那么则用掉一块饼干, index–;否则,不能满足孩子的胃口,则饼干用不掉。再一个sort函数需要algorithm头文件。
??程序如下

class Solution {
public:
	int findContentChildren(vector<int>& g, vector<int>& s) {
		sort(g.begin(), g.end());
		sort(s.begin(), s.end());
		int index = s.size() - 1;	// 饼干的索引
		int result = 0;
		for (int i = g.size() - 1; i >= 0; i--) {	// i 代表孩子胃口的索引
			if (index >= 0 && s[index] >= g[i]) {
				index--;	// 用掉一块饼干
				result++;	// 满足了一位孩子
			}
		}
		return result;
	}
};

复杂度分析:

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
  • 空间复杂度: O ( 1 ) O(1) O(1)

三、完整代码

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

class Solution {
public:
	int findContentChildren(vector<int>& g, vector<int>& s) {
		sort(g.begin(), g.end());
		sort(s.begin(), s.end());
		int index = s.size() - 1;	// 饼干的索引
		int result = 0;
		for (int i = g.size() - 1; i >= 0; i--) {	// i 代表孩子胃口的索引
			if (index >= 0 && s[index] >= g[i]) {
				index--;	// 用掉一块饼干
				result++;	// 满足了一位孩子
			}
		}
		return result;
	}
};

int main() {
	vector<int> g = { 1, 2, 3 };	// 孩子的胃口
	vector<int> s = { 1, 1 };		// 饼干的大小
	Solution s1;
	int result = s1.findContentChildren(g, s);
	cout << result << endl;
	system("pause");
	return 0;
}

end

文章来源:https://blog.csdn.net/qq_45765437/article/details/134988077
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。