2025-09-07：水果成篮Ⅱ。用go语言，给定两个长度为 n 的整型数组 f

健康生活 2025年09月07日 12:00 4 admin

2025-09-07：水果成篮Ⅱ。用go语言，给定两个长度为 n 的整型数组 fruits 和 baskets，前者 fruits[i] 表示第 i 类水果的数量，后者 baskets[j] 表示第 j 个篮子的容量上限。

按以下步骤将水果依序放入篮子：

• 按 fruits 索引从小到大逐一处理每一类水果；

• 对于当前这类水果，要放入从左到右第一个尚未被占用且容量至少等于该类数量的篮子；

• 每个篮子只能被一种水果占用，一旦占用就不能再用；

• 若找不到满足条件的篮子，则该类水果保持未放置状态。

最终返回完成上述过程后，仍未被放入任何篮子的水果种类数量。

n == fruits.length == baskets.length。

1 <= n <= 100。

1 <= fruits[i], baskets[i] <= 1000。

输入： 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。

题目来自力扣3477。

步骤描述：

1. 初始化：

• 我们有一个水果数组 fruits，其中每个元素 fruits[i] 表示第 i 类水果的数量。

• 我们有一个篮子数组 baskets，其中每个元素 baskets[j] 表示第 j 个篮子的容量上限。

• 我们需要按索引从小到大（即从 fruits[0] 到 fruits[n-1]）逐一处理每一类水果。

2. 处理每一类水果：

• 对于当前正在处理的水果 fruit（即 fruits[i]），我们需要找到一个篮子来放置它。

• 查找篮子的规则是：从左到右（即从 baskets[0] 到 baskets[n-1]）扫描篮子数组，寻找第一个尚未被占用（即篮子容量值未被置零）且容量至少等于当前水果数量（即 baskets[j] >= fruit）的篮子。

• 如果找到这样的篮子：

• 将该篮子的容量置为零（标记为已被占用，防止后续水果再次使用）。

• 标记当前水果已被放置（即 unset 为0），并继续处理下一个水果。

• 如果找不到这样的篮子（即扫描完所有篮子都没有满足条件的）：

• 当前水果无法被放置，计数 count 增加1（因为 unset 保持为1）。

3. 重复处理：

• 对每一类水果重复上述过程，直到所有水果都被处理完毕。

4. 返回结果：

• 最终返回 count，即未被放入任何篮子的水果种类数量。

具体例子（输入：fruits = [4,2,5], baskets = [3,5,4]）：

• 处理第一类水果（4）：

从左扫描篮子：第一个篮子容量为3（3<4，不满足），第二个篮子容量为5（5>=4，满足且未被占用）-> 占用第二个篮子（将其置0），此时baskets变为[3,0,4]。

• 处理第二类水果（2）：

从左扫描篮子：第一个篮子容量为3（3>=2，满足且未被占用）-> 占用第一个篮子（将其置0），此时baskets变为[0,0,4]。

• 处理第三类水果（5）：

从左扫描篮子：第一个篮子已被占用（值为0），第二个篮子已被占用（值为0），第三个篮子容量为4（4<5，不满足）-> 找不到可用篮子，计数增加1。

• 返回计数1。

复杂度分析：

• 时间复杂度：
对于每个水果（共n个），我们最坏情况下需要遍历整个篮子数组（长度n）来寻找可用的篮子。因此，总的时间复杂度为 O(n²)。

• 额外空间复杂度：
我们只使用了常数个额外变量（如count、unset和循环变量），没有使用与输入规模相关的额外数据结构。因此，总的额外空间复杂度为 O(1)。

注意：虽然我们修改了原始的baskets数组（原地标记占用），但题目允许修改（根据代码逻辑），且这并不算额外空间（因为输入数组本身可被修改）。所以额外空间复杂度是常数。

Go完整代码如下：

package mainimport (    "fmt")func numOfUnplacedFruits(fruits []int, baskets []int)int {    count := 0    n := len(baskets)    for _, fruit := range fruits {        unset := 1        for i := 0; i < n; i++ {            if fruit <= baskets[i] {                baskets[i] = 0                unset = 0                break            }        }        count += unset    }    return count}func main() {    fruits := []int{4, 2, 5}    baskets := []int{3, 5, 4}    result := numOfUnplacedFruits(fruits, baskets)    fmt.Println(result)}

2025-09-07：水果成篮Ⅱ。用go语言，给定两个长度为 n 的整型数组 f

Python完整代码如下：

# -*-coding:utf-8-*-def num_of_unplaced_fruits(fruits, baskets):    count = 0    n = len(baskets)    for fruit in fruits:        unset = 1        for i in range(n):            if fruit <= baskets[i]:                baskets[i] = 0                unset = 0                break        count += unset    return countif __name__ == "__main__":    fruits = [4, 2, 5]    baskets = [3, 5, 4]    result = num_of_unplaced_fruits(fruits, baskets)    print(result)