【Day 65 】2023-01-04 - 455. 分发饼干

[azl397985856]

455. 分发饼干

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/assign-cookies/

前置知识

暂无

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 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.

[buer1121]

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int:

逆序，先考虑大胃口

    g.sort()
    s.sort()
    start,count=len(s)-1,0
    for idc in range(len(g)-1,-1,-1):
        if start>=0 and g[idc]<=s[start]:
            count+=1
            start-=1
    return count

[ringo1597]

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int m = g.length, n = s.length;
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
}

[klspta]

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int ans = 0;
        int idx = 0;
        for(int i = 0; i < g.length; i++){
            while(idx < s.length && g[i] > s[idx]){
                idx++;
            }
            if(idx < s.length && g[i] <= s[idx]){
                ans++;
                idx++;
            }
        }
        return ans;
    }
}

[FlipN9]

/**
    Greedy: O(mlogm+nlogn)  SC: (logm+logn)
*/
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int gL = g.length, sL = s.length;
        int count = 0;

        int i = 0, j = 0;
        while (i < gL && j < sL) {
            if (s[j] >= g[i])
                i++;
            j++;
        }
        return i;
    }
}

[bookyue]

code

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0;
        int j = 0;
        while (i < g.length && j < s.length) {
            if (g[i] <= s[j]) i++;
            j++;
        }

        return i;
    }

[chenming-cao]

解题思路

贪心。我们只能把不小于孩子胃口值的饼干给孩子，并且每块饼干最多只能给1个孩子。我们可以分别对孩子们按胃口值从小到大排序，对饼干按尺寸从小到大排序，将排好序的两个数组同时向后遍历，优先满足胃口值小的孩子。最后返回结果即可。

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // sort g and s, easy to compare
        Arrays.sort(g);
        Arrays.sort(s);
        int gidx = 0, sidx = 0;
        int res = 0;
        while (gidx < g.length && sidx < s.length) {
            // we can assign the cookie
            if (g[gidx] <= s[sidx]) {
                res++;
                gidx++;
                sidx++;
            }
            // we cannot assign the cookie, check next cookie
            else {
                sidx++;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，因为要排序
• 空间复杂度：O(1)

[Elsa-zhang]

# 455 分发饼干
''' 从大到小排序
    饼干>胃口 count+1
'''

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]):
        g = sorted(g, reverse=True)
        s = sorted(s, reverse=True)
        count = 0
        gg,ss = 0,0
        while gg<len(g) and ss<len(s):
            if s[ss]>=g[gg]:
                ss+=1
                count+=1
            gg+=1
        return count

g = [1,2,3]
s = [1,1]
solution = Solution()
ans = solution.findContentChildren(g, s)
print(ans)

[AstrKing]

思路

先对两个数组进行排序，定义初始值0，然后遍历进行比较，如果说能满足小孩，那么初始值+1，一直这么遍历到尾部即可

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (g[i] <= s[j]) {
                res++;
                i++;
                j++;
            } else if (g[i] > s[j]) {
                j++;
            }
        }
        return res;

    }
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[snmyj]

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int m=g.size(),n=s.size(),cnt=0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(s[j]>=g[i]) {
                    cnt++;
                   s.erase(s.begin()+j);
                   break;
                    }

            }
        }
        return cnt;
    }
};

[jackgaoyuan]

func findContentChildren(g []int, s []int) (res int) {
    sort.Ints(g)
    sort.Ints(s)
    gFlag, sFlag := 0, 0
    for gFlag < len(g) && sFlag < len(s) {
        if g[gFlag] <= s[sFlag] {
            res++
            gFlag++
        }
        sFlag++
    }
    return
}

[zenwangzy]

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort(reverse=True)
        s.sort(reverse=True)
        gi, si = 0, 0
        count = 0

        while si < len(s) and gi < len(g):
            if g[gi] <= s[si]:
                gi += 1
                si += 1
                count += 1
            else:
                gi += 1
        return count

时间复杂度：由于使用了排序，因此时间复杂度大约为 O(nlogn)

空间复杂度：取决于具体的排序方法

[whoam-challenge]

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() m, n = len(g), len(s) i = j = count = 0

    while i < m and j < n:
        while j < n and g[i] > s[j]:
            j += 1
        if j < n:
            count += 1
        i += 1
        j += 1

    return count

[A-pricity]

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    // i：胃口的索引，j：尺寸的索引
    let [index,i,j] = [0,0,0];
    g.sort((a,b)=>a-b);
    s.sort((a,b)=>a-b);
    while(i<g.length && j<s.length){
        if(g[i] <= s[j]){ // 若是当前尺寸满足胃口，进行下一组对比
            index++;
            i++;
            j++;
        }else if(g[i] > s[j]){ // 当前尺寸不满足胃口，对比下一个尺寸
            j++;
        }
    }
    return index;
};

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        //从数组最大值开始遍历
        for(int i = g.length-1,j = s.length-1; i >= 0 && j >= 0;){
            if(s[j] >= g[i]){
                count++;
                j--;
                i--;
            }else{
                i--;
            }
        }
        return count;

    }
}

[tiandao043]

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int ans=0;
        int l=0,r=0;
        while(r<s.size()&&l<g.size()){
            if(s[r]>=g[l]){
                ans++;
                r++;
                l++;
            }
            else{
                r++;
            }
        }
        return ans;
    }
};

O(nlogn) O(logn)

[liuajingliu]

var findContentChildren = function(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    const m = g.length, n = s.length;
    let count = 0;
    for (let i = 0, j = 0; i < m && j < n; i++, j++) {
        while (j < n && g[i] > s[j]) {
            j++;
        }
        if (j < n) {
            count++;
        }
    }
    return count;
};

[AtaraxyAdong]

class Solution {
    public int findContentChildren(int[] g, int[] s) {

        int childrenNums = g.length, cookiesNums = s.length,
                res = 0, maxContentNum = Math.min(childrenNums, cookiesNums);
        Arrays.sort(g);
        Arrays.sort(s);

        int currentChild = 0, currentCookie = 0;

        while (res < maxContentNum && currentCookie < cookiesNums && currentChild < childrenNums) {
            // 当前 cookie 可以满足这个孩子
            if (g[currentChild] <= s[currentCookie]) {
                res++;
                currentCookie++;
                currentChild++;
            } else {
                currentCookie++;
            }
        }

        return res;
    }
}

[paopaohua]

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int m = g.length, n = s.length;
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
}

[saitoChen]

思路

贪心算法

代码

const findContentChildren = (g, s) => {
  g.sort((a, b) => a - b)
  s.sort((a, b) => a - b)
  let result = 0
  let cookieIndex = s.length - 1
  for (let i = g.length - 1; i >= 0; i--) {
    if (cookieIndex >= 0 && s[cookieIndex] >= g[i]) {
      result++
      cookieIndex--
    }
  }

  return result
};

[RestlessBreeze]

code

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int m = g.size(), n = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
};

[GG925407590]

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int m = g.size(), n = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
};

[mayloveless]

思路

先排序，遍历孩子，匹配饼干

代码

var findContentChildren = function(g, s) {
    g.sort((a,b) => a - b);
    s.sort((a,b) => a - b);

    let res = 0;
    let sIndex = 0;
    for (let i =0;i<g.length;i++) {
        for (let j = sIndex;j<s.length;j++) {
            if (g[i] <= s[j]) {
                sIndex = j + 1;
                res ++;
                break;
            }
        }
    }

    return res;
};

复杂度

时间O(mlogm+nlogn) 排序开销 空间：O(logm+logn)

[zywang0]

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (g[i] <= s[j]) {
                res++;
                i++;
                j++;
            } else if (g[i] > s[j]) {
                j++;
            }
        }
        return res;

    }
}

[Ryanbaiyansong]

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 每个孩子最多一个cookie
        g.sort()
        s.sort()
        ans = 0
        i = j = 0
        m, n = len(g), len(s)
        while i < m and j < n:
            if g[i] <= s[j]:
                ans += 1
                i += 1
                j += 1
            else:
                j += 1

        return ans

[Jetery]

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            if (ans < g.size() && g[ans] <= s[i]) ans++;
        }
        return ans;
    }
};