题目描述
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示:
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
数据结构
- 数组
算法思维
- 遍历、贪心
解题思路
一. Comprehend 理解题意
- 尽可能多的匹配两个数组中的值
- 匹配规则:数组一的值不大于数组二的值
二. Choose 选择数据结构与算法
贪心算法
- 数据结构:数组
- 算法思维:遍历、贪心
- 解题思路
1)先将两个两数组进行排序,保证孩子的胃口和饼干的大小都从小到大排列
2)以孩子的胃口为准,进行贪心匹配
3)如果 当前饼干 >= 当前孩子的胃口,继续判断下一块饼干和下一个孩子
4)如果 当前饼干 < 当前孩子的胃口,继续判断下一块饼干和当前孩子
5)直到饼干或孩子被遍历结束,返回被满足的孩子的数量 - 核心要点:
1)排序的好处:如果当前孩子不能被满足,则其后的孩子肯定也不能被满足,因为胃口是越来越大的
2)遍历结束时:孩子数组的下标即为被满足的孩子的数量
三. Code 编码实现基本解法
class Solution {
public int findContentChildren(int[] g, int[] s) {
int gl = g.length;
int sl = s.length;
//非空判断
if (gl == 0 || sl == 0) return 0;
//分别对两个数组进行排序(自编快速排序)
quickSort(g, 0, gl - 1);
quickSort(s, 0, sl - 1);
//这里数组的排序也可以使用 Java API 实现
//Arrays.sort(g);
//Arrays.sort(s);
//以小孩为准进行贪心匹配
int i = 0, j = 0;
while (j < sl && i < gl) {
if (s[j] >= g[i]) i++;
j++;
}
//返回被满足的小孩数量
return i;
}
public void quickSort(int[] target, int low, int high) {
int left = low;
int right = high;
int standard = target[left];
while (left < right) {
while (left < right && target[right] >= standard) right--;
if (left < right) target[left++] = target[right];
while (left < right && target[left] <= standard) left++;
if (left < right) target[right--] = target[left];
}
target[left] = standard;
if (left > low + 1) quickSort(target, low, left - 1);
if (right < high - 1) quickSort(target, right + 1, high);
}
}
执行耗时:8 ms,击败了 86.63% 的Java用户
内存消耗:39.2 MB,击败了 55.67% 的Java用户
时间复杂度:O(n)
• 两个数组的遍历 O(n)
空间复杂度:O(1)
• 两个指针变量,占用常数级内存空间 O(1)
四. Consider 思考更优解
=== 待续 ===
五. Code 编码实现最优解
=== 待续 ===
六. Change 变形与延伸
=== 待续 ==