Easy

题目描述

给你两个长度为 n 的整数数组 fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的数量，baskets[j] 表示第 j 个篮子的容量。

从左到右，根据以下规则放置水果：

  • 每种水果类型必须放在容量大于或等于该水果类型数量的最左边可用的篮子中。
  • 每个篮子只能装一种水果。
  • 如果某种水果类型无法放在任何篮子中，则它保持未放置状态。

返回在完成所有可能的分配后仍然未放置的水果类型数量。

示例 1：

输入：fruits = [4,2,5], baskets = [3,5,4]
输出：1
解释：
- fruits[0] = 4 被放在 baskets[1] = 5 中。
- fruits[1] = 2 被放在 baskets[0] = 3 中。
- fruits[2] = 5 无法被放在 baskets[2] = 4 中。
由于有一种水果类型未被放置，返回 1。

示例 2：

输入：fruits = [3,6,1], baskets = [6,4,7]
输出：0
解释：
- fruits[0] = 3 被放在 baskets[0] = 6 中。
- fruits[1] = 6 无法被放在 baskets[1] = 4 中（容量不足），但可以被放在下一个可用的篮子 baskets[2] = 7 中。
- fruits[2] = 1 被放在 baskets[1] = 4 中。
由于所有水果都成功放置，返回 0。

约束条件：

  • n == fruits.length == baskets.length
  • 1 <= n <= 100
  • 1 <= fruits[i], baskets[i] <= 1000

解题思路

这是一个模拟题，我们需要按照题目描述的规则来分配水果到篮子中。

解题思路：

  1. 贪心模拟：按照水果的顺序，为每种水果找到最左边的可用篮子
  2. 状态维护：用一个布尔数组记录每个篮子是否已被使用
  3. 查找策略：对于每种水果，从左到右遍历篮子，找到第一个容量足够且未被使用的篮子

算法步骤：

  • 初始化一个布尔数组 used 记录篮子的使用状态
  • 对于每种水果，从左到右遍历所有篮子
  • 如果找到容量足够且未使用的篮子，标记为已使用并继续下一种水果
  • 如果遍历完所有篮子都没找到合适的，计数器加一
  • 返回未放置的水果数量

时间复杂度分析：

  • 外层循环遍历 n 种水果
  • 内层循环最多遍历 n 个篮子
  • 总时间复杂度：O(n²)

空间复杂度分析：

  • 使用额外的布尔数组记录篮子状态：O(n)

代码实现

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = fruits.size();
        vector<bool> used(n, false);
        int unplaced = 0;
        
        for (int i = 0; i < n; i++) {
            bool placed = false;
            for (int j = 0; j < n; j++) {
                if (!used[j] && baskets[j] >= fruits[i]) {
                    used[j] = true;
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                unplaced++;
            }
        }
        
        return unplaced;
    }
};

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        used = [False] * n
        unplaced = 0
        
        for i in range(n):
            placed = False
            for j in range(n):
                if not used[j] and baskets[j] >= fruits[i]:
                    used[j] = True
                    placed = True
                    break
            if not placed:
                unplaced += 1
        
        return unplaced

public class Solution {
    public int NumOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.Length;
        bool[] used = new bool[n];
        int unplaced = 0;
        
        for (int i = 0; i < n; i++) {
            bool placed = false;
            for (int j = 0; j < n; j++) {
                if (!used[j] && baskets[j] >= fruits[i]) {
                    used[j] = true;
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                unplaced++;
            }
        }
        
        return unplaced;
    }
}

var numOfUnplacedFruits = function(fruits, baskets) {
    const n = fruits.length;
    const used = new Array(n).fill(false);
    let unplaced = 0;
    
    for (let i = 0; i < n; i++) {
        let placed = false;
        for (let j = 0; j < n; j++) {
            if (!used[j] && baskets[j] >= fruits[i]) {
                used[j] = true;
                placed = true;
                break;
            }
        }
        if (!placed) {
            unplaced++;
        }
    }
    
    return unplaced;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环 n 次，内层循环最多 n 次
空间复杂度O(n)使用额外的布尔数组记录篮子使用状态

相关题目