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

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. 1. 初始化：
   • • 我们有一个水果数组 fruits，其中每个元素 fruits[i] 表示第 i 类水果的数量。
   • • 我们有一个篮子数组 baskets，其中每个元素 baskets[j] 表示第 j 个篮子的容量上限。
   • • 我们需要按索引从小到大（即从 fruits[0] 到 fruits[n-1]）逐一处理每一类水果。
2. 2. 处理每一类水果：
   • • 对于当前正在处理的水果 fruit（即 fruits[i]），我们需要找到一个篮子来放置它。
   • • 查找篮子的规则是：从左到右（即从 baskets[0] 到 baskets[n-1]）扫描篮子数组，寻找第一个尚未被占用（即篮子容量值未被置零）且容量至少等于当前水果数量（即 baskets[j] >= fruit）的篮子。
   • • 如果找到这样的篮子：
     • • 将该篮子的容量置为零（标记为已被占用，防止后续水果再次使用）。
     • • 标记当前水果已被放置（即 unset 为0），并继续处理下一个水果。
   • • 如果找不到这样的篮子（即扫描完所有篮子都没有满足条件的）：
     • • 当前水果无法被放置，计数 count 增加1（因为 unset 保持为1）。
3. 3. 重复处理：
   • • 对每一类水果重复上述过程，直到所有水果都被处理完毕。
4. 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 main

import (
    "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)
}

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 count

if __name__ == "__main__":
    fruits = [4, 2, 5]
    baskets = [3, 5, 4]
    result = num_of_unplaced_fruits(fruits, baskets)
    print(result)

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。 欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展