【Day 65 】2023-04-19 - 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.

[Meisgithub]

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

[Zoeyzyzyzy]

class Solution {
    // 贪心策略： 不考虑整体情况，每次只找出局部最优解。 为了让分到饼干的人数最多，先从胃口最小的孩子算起。
    // TC: O(nlogN)(排序的时间复杂度) SC: O(1) 只需要两个指针来记录。
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int p = 0, q = 0;
        int ans = 0;
        while (p < g.length && q < s.length) {
            if (g[p] <= s[q]) {
                p++;
                q++;
                ans++;
            } else {
                q++;
            }
        }
        return ans;
    }
}

[JasonQiu]

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        heapq.heapify(g)
        heapq.heapify(s)
        result = 0
        while g and s:
            if s[0] >= g[0]:
                heapq.heappop(g)
                result += 1
            heapq.heappop(s)
        return result

Time: O(mlogm+nlogn) Space: O(1)

[kofzhang]

思路

贪心算法

复杂度

时间复杂度：O(mlogm+nlogn) 空间复杂度：O(1)

代码

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

[lp1506947671]

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        s.sort(reverse=True)
        g.sort(reverse=True)
        gi, si = 0, 0
        count = 0
        while gi < len(g) and si < len(s):
            if s[si] >= g[gi]:
                count += 1
                si += 1
            gi += 1
        return count

复杂度分析

令 n 为数组长度

• 时间复杂度：由于使用了排序，因此时间复杂度大约为 O(nlogn)
• 空间复杂度：取决于具体的排序方法，大概是 O(1) 到 O(logn)

[NorthSeacoder]

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    let res = 0;
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    let i = g.length - 1;
    let j = s.length - 1;
    while (i >= 0) {
        if (j >= 0 && g[i] <= s[j]) {
            j--;
            res++;
        }
        i--;
    }
    return res;
};

[xb798298436]

const findContentChildren = function (g, s) {
  g = g.sort((a, b) => a - b);
  s = s.sort((a, b) => a - b);
  let gi = 0; // 胃口值
  let sj = 0; // 饼干尺寸
  let res = 0;
  while (gi < g.length && sj < s.length) {
    // 当饼干 sj >= 胃口 gi 时，饼干满足胃口，更新满足的孩子数并移动指针
    if (s[sj] >= g[gi]) {
      gi++;
      sj++;
      res++;
    } else {
      // 当饼干 sj < 胃口 gi 时，饼干不能满足胃口，需要换大的
      sj++;
    }
  }
  return res;
};

[Diana21170648]

思路

贪心，先用一个饼干遍历最小胃口的孩子，满足不了，更换饼干，满足最小孩子的胃口，换下一个孩子

class Solution:
    def assigncookies(self,gi,Sj)->int:
        Sj.sort#倒序排列,饼干大小
        gi.sort#孩子胃口大小
        S,g=0,0
        count=0

        while S<len(Sj) :#遍历所有饼干
            while g<len(gi):#孩子
                if Sj[S]<gi[g]:#饼干的大小不bu满足最小孩子的胃口
                    S+=1
                else:
                    count+=1
                    S+=1
                break
                g+=1   
        return count
Solution().assigncookies([1,2,3],[1,2])

**复杂度分析**
- 时间复杂度：O(NlogN)，使用了排序。
- 空间复杂度：O(N)

[wangqianqian202301]

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

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

[aoxiangw]

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

O(nlogn), O(1)

[Abby-xu]

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        gs,ss = sorted(g),sorted(s)
        c = 0
        while ss and gs:
            if ss[-1] >= gs[-1]:
                ss.pop()
                c += 1
            gs.pop()
        return c

[csthaha]

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    const sortG = g.sort((a, b) => a - b),
          sortS = s.sort((a, b) => a - b);
    if(s.length === 0) return 0;
    let i = 0,
        j = 0;
    while(i < sortG.length && j < sortS.length){
        if(sortG[i] <= sortS[j]) {
            i++;
        }
        j++;
    }
    return i;
};

[RestlessBreeze]

code

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int glength = g.size() - 1;
        int slength = s.size() - 1;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int res = 0;
        while (slength >= 0 && glength >= 0)
        {
            while (glength >= 0 && s[slength] < g[glength])
                glength--;
            if (glength < 0)
                break;
            slength--;
            glength--;
            res++;
        }
        return res;
    }
};

[FireHaoSky]

思路：贪心

代码：python

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g = sorted(g)
        s = sorted(s)
        g_len = len(g)
        i = 0
        count = 0
        for j, x in enumerate(s):
            if x >= g[i]:
                count += 1
                i += 1
            if i == g_len:
                break
        return count

复杂度分析：

"""
时间复杂度：O(mlogm+nlogn)
空间复杂度：O(logm+logn)
"""

[sye9286]

思路

先排序，然后用贪心算法，从小到大用最小的饼干满足每个孩子的胃口

代码

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

复杂度分析

• 时间复杂度：O(m log m + n log n)
• 空间复杂度：O(log m + log n)

[chocolate-emperor]

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 i = 0,j = 0;
        int cnt = 0;
        while(i<m && j<n){
            if(g[i]<=s[j])  {
                cnt+=1;
                i++;
                j++;
            }else{
                j+=1;
            }
        }
        return cnt;
    }
};

[chanceyliu]

代码

function findContentChildren(g: number[], s: number[]): number {
  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;
};

[jiujingxukong]

思路

贪心。排序。两个指针。一个饼干不能满足胃口，就换更大的饼干。

代码

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function (g, s) {
  //这里的排序函数不能写花括号，就像s.sort((a, b) => {
    a - b;
  });这样，是不对的，箭头函数无返回值，就无法排序。
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  let gm = 0;
  let sn = 0;
  let res = 0;
  while (gm < g.length && sn < s.length) {
    if (s[sn] >= g[gm]) {
      res += 1;
      gm++;
    }
    sn++;
  }
  return res;
};

复杂度分析

• 时间复杂度：由于使用了排序，因此时间复杂度大约为 O(nlogn)
• 空间复杂度：取决于具体的排序方法，大概是 O(1) 到 O(logn)

[harperz24]

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):
            while j < len(s) and g[i] > s[j]:
                j += 1
            if j < len(s):
                res += 1
            i += 1
            j += 1

        return res

        # time: O(mlogm+nlogn)
        # space: O(logm+logn)

[61hhh]

思路

双指针 i 和 j 分别遍历两个数组

代码

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

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

[zhangyu1131]

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 先排个序
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        // 双指针
        int child_idx = 0, candy_idx = 0;
        int n = g.size(), m = s.size();
        while (child_idx < n && candy_idx < m)
        {
            if (s[candy_idx] >= g[child_idx])
            {
                candy_idx++;
                child_idx++;
            }
            else
            {
                candy_idx++;
            }
        }

        return child_idx;
    }
};

[bookyue]

TC: O(nlogn + mlogm)
SC: O(1)

    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;
    }

[GuitarYs]

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

[Lydia61]

455. 分发饼干

思路

排序、双指针

代码

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;
    }
};

复杂度分析

• 时间复杂度：O(nlogn + nlogm)
• 空间复杂度：O(logn + logm)

[kangliqi1]

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;

}

}

[joemonkeylee]

代码

       public int FindContentChildren(int[] g, int[] s)
        {
            int count = 0;
            Array.Sort(g);
            Array.Sort(s);
            int gCount = g.Length;
            int sCount = s.Length;
            int gIndex = 0;
            int sIndex = 0;
            while (gIndex < gCount && sIndex < sCount)
            {
                if (g[gIndex] <= s[sIndex])
                {
                    count++;
                    gIndex++;
                }
                sIndex++;
            }
            return count;
        }

• 时间复杂度：O(nlogn+mlogm)
• 空间复杂度：O(logn+logm)

[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;
    }
};

[yingchehu]

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        kid = 0
        for cookie in s:
            if cookie >= g[kid]:
                kid += 1
            if kid == len(g):
                break

        return kid

[Hughlin07]

class Solution {

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);

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

}

[snmyj]

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int cnt=0,index=0,amount=s.size();
        for(int i=0;i<g.size();i++){

            for(int j=index;j<s.size();j++){
                if(s[j]>=g[i]&&amount>0){ 
                    cnt++;
                    amount--;
                    break;
                    index=j;
                    }
            }
             if(amount==0) break;

        }
        return cnt;
    }
};

[Fuku-L]

代码

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;
    }
}