算法 2.5.1 分发饼干【leetcode 455】

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 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 * 10⁴
0 <= s.length <= 3 * 10⁴
1 <= g[i], s[j] <= 2³¹ - 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 编码实现最优解