leetcode Greedy Algorithm

leetcode 455题

Posted by franki on February 10, 2021

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.

思路

贪心算法

代码

var findContentChildren = function(g, s) {
    // 先排序
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    const gLen = g.length;
    const sLen = s.length;
    // 定义i,j两个指针分别指向孩子、饼干
    let i=0, j=0, num = 0;
    // 循环结束条件，当i,j两者有其一超过数组的边界即停止
    while (i < gLen && j < sLen) {
        // 当当前饼干大于或等于当前胃口，i,j指针都向前移动；否则，只移动j指针
        if (s[j] >= g[i]) {
            num++;
            j++;
            i++;
        } else {
            j++;
        }
    }
    return num;
};

复杂度分析

  • 时间复杂度: O(mlogm + nlogn)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS