跳转至

3477. 水果成篮 II

题目描述

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

你需要对 fruits 数组从左到右按照以下规则放置水果：

  • 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
  • 每个篮子只能装 一种 水果。
  • 如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

 

示例 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

解法

方法一：模拟

思考

每个水果放进最左侧容量足够且尚未使用的篮子。数据规模允许对每个水果扫描全部篮子。

需要标记已用篮子，否则同一篮子会被重复占用。

布尔数组 \(\textit{vis}\) 记录占用。水果从左到右，篮子同样从左到右找第一只合格者；找不到则计入未放置数。

我们用一个长度为 \(n\) 的布尔数组 \(\textit{vis}\) 记录已经被使用的篮子，用一个答案变量 \(\textit{ans}\) 记录所有未被放置的水果，初始时 \(\textit{ans} = n\)。

接下来，我们遍历每一种水果 \(x\)，对于当前水果，我们遍历所有的篮子，找出第一个未被使用，且容量大于等于 \(x\) 的篮子 \(i\)。如果找到了，那么答案 \(\textit{ans}\) 减 \(1\)。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{fruits}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        vis = [False] * n
        ans = n
        for x in fruits:
            for i, y in enumerate(baskets):
                if y >= x and not vis[i]:
                    vis[i] = True
                    ans -= 1
                    break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.length;
        boolean[] vis = new boolean[n];
        int ans = n;
        for (int x : fruits) {
            for (int i = 0; i < n; ++i) {
                if (baskets[i] >= x && !vis[i]) {
                    vis[i] = true;
                    --ans;
                    break;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = fruits.size();
        vector<bool> vis(n);
        int ans = n;
        for (int x : fruits) {
            for (int i = 0; i < n; ++i) {
                if (baskets[i] >= x && !vis[i]) {
                    vis[i] = true;
                    --ans;
                    break;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func numOfUnplacedFruits(fruits []int, baskets []int) int {
    n := len(fruits)
    ans := n
    vis := make([]bool, n)
    for _, x := range fruits {
        for i, y := range baskets {
            if y >= x && !vis[i] {
                vis[i] = true
                ans--
                break
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function numOfUnplacedFruits(fruits: number[], baskets: number[]): number {
    const n = fruits.length;
    const vis: boolean[] = Array(n).fill(false);
    let ans = n;
    for (const x of fruits) {
        for (let i = 0; i < n; ++i) {
            if (baskets[i] >= x && !vis[i]) {
                vis[i] = true;
                --ans;
                break;
            }
        }
    }
    return ans;
}

评论