美文网首页
Leetcode_455_分发饼干_hn

Leetcode_455_分发饼干_hn

作者: 1只特立独行的猪 | 来源:发表于2020-03-23 11:18 被阅读0次

    题目描述

    假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

    注意:
    你可以假设胃口值为正。
    一个小朋友最多只能拥有一块饼干。

    示例

    示例 1:

    输入: [1,2,3], [1,1]
    
    输出: 1
    
    解释: 
    你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
    虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
    所以你应该输出1。
    

    示例2:

    输入: [1,2], [1,2,3]
    
    输出: 2
    
    解释: 
    你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
    你拥有的饼干数量和尺寸都足以让所有孩子满足。
    所以你应该输出2.
    

    解答方法

    方法一:双指针法

    思路

    对给出的g数组和s数组排序
    初始化i,j指针为0,分别用于扫描g和s,若有满足g[i] <= s[j],则更新满足的数量ans
    直到g或者s被全部扫描完,返回ans

    代码

    class Solution:
        def findContentChildren(self, g: List[int], s: List[int]) -> int:
            g.sort()
            s.sort()
            i = 0
            j = 0
            res = 0
            while i <len(g) and j < len(s):
                if g[i] <= s[j]:
                    res += 1
                    i += 1
                    j += 1
                else:
                    j += 1
            return res
    

    时间复杂度

    O(Nlog(N))排序算法的复杂度

    空间复杂度

    O(1) 未申请额外的空间

    相关文章

      网友评论

          本文标题:Leetcode_455_分发饼干_hn

          本文链接:https://www.haomeiwen.com/subject/dcwiyhtx.html