[LeetCode] (455) Assign Cookies 派饼干

题干大意:有若干个熊孩子和若干个大小不一的饼干,每个熊孩子都有一个贪心指数,如果拿不到那么大的饼干就伐开心。要求满足足够多的熊孩子。

核心思路:通过贪心算法,优先满足比较容易满足的熊孩子,并且尽可能地派出饼干。

实现方式甲:

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        count = 0
        start = 0
        for greed in g:
            for i, size in enumerate(s[start:]):
                if size >= greed:
                    count += 1
                    start += i + 1
                    break
        return count

算法复杂度为 O(n)

 

实现方式乙:

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        count = 0
        for size in s:
            if count < len(g) and size >= g[count]:
                count += 1
        return count

算法复杂度同样为 O(n)

Related posts