2025-09-09：水果成篮Ⅲ。用go语言，给你两个等长的整数数组 fruits 和 baskets：fruits[i] 表示|baskets|count|fruits|self|tree|水果成篮ⅲ

2025-09-09：水果成篮Ⅲ。用go语言，给你两个等长的整数数组 fruits 和 baskets：fruits[i] 表示第 i 类水果的数量，baskets[j] 表示第 j 个篮子的容量。按 fruits 的索引从小到大依次处理每一类水果：对于当前水果，找出下标最小且尚未被占用、容量不少于该水果数量的篮子，把这类水果放入；每个篮子最多放一种水果；若不存在符合条件的空篮子，则该类水果保持未放置。所有水果处理完后，返回仍然未被放入任何篮子的水果种类数。

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

1 <= n <= 100000。

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

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

题目来自力扣3479。

分步骤描述过程

1.初始化：

• 首先，检查篮子数组baskets的长度。如果长度为0（即没有篮子），则所有水果都无法放置，直接返回水果的种类数（即len(fruits)）。
• 否则，初始化一个线段树（SegTree）结构，用于高效地查询和更新篮子的状态。线段树节点数组segNode的大小为4 * m + 7（其中m是篮子的数量），篮子数组baskets被存储在线段树中。

2.构建线段树：

• 线段树构建函数build被调用，递归地将篮子数组构建成线段树。每个叶子节点存储对应篮子的容量，内部节点存储其左右子树的最大值（即区间内的最大篮子容量）。

3.处理每类水果：

• 遍历每类水果（按索引从小到大）：
- • 对于当前水果fruits[i]，使用二分查找（在线段树上）寻找下标最小的、容量不小于fruits[i]且尚未被占用的篮子。
- - • 二分查找的区间为[0, m-1]（即所有篮子）。
  - • 对于每个中间位置mid，查询线段树区间[0, mid]的最大值。如果该最大值大于等于当前水果的数量，说明存在符合条件的篮子（且下标最小的在左半部分），继续在左半部分查找；否则在右半部分查找。
- • 如果找到了这样的篮子（res != -1）并且该篮子的容量确实大于等于水果数量（实际上通过线段树查询已经保证了这一点），则将该篮子标记为已被占用（通过线段树更新将该篮子的容量设置为INT_MIN，这样后续查询就不会再找到它）。
- • 如果没有找到符合条件的篮子，则未放置的水果种类数count加1。

4.返回结果：

• 处理完所有水果后，返回未放置的水果种类数count。

总的时间复杂度和总的额外空间复杂度

•时间复杂度：
- • 构建线段树：O(m)，其中 m 是篮子的数量。
- • 处理每类水果：对于每类水果，进行二分查找（每次二分查找需要 O(log m) 时间），每次二分查找中需要在线段树上查询（每次查询也是 O(log m) 时间），并且如果找到篮子还需要更新线段树（一次更新也是 O(log m) 时间）。因此处理每类水果的总时间是 O(log² m)（因为二分查找和线段树操作都是对数时间）。
- • 总共有 n 类水果，所以总时间复杂度为 O(n * log² m)。由于 n 和 m 等长（题目中 n == m），所以可以表示为 O(n * log² n)。
•额外空间复杂度：
- • 线段树需要 O(m) 的额外空间（即 4 * m + 7），因此额外空间复杂度为 O(m)。由于 m = n，所以为 O(n)。

总结：

• 时间复杂度：O(n * log² n)
• 额外空间复杂度：O(n)

Go完整代码如下：

package main import (     "fmt"     "math" ) const (     INT_MIN = math.MinInt32 ) type SegTree struct {     segNode []int     baskets []int } func (this *SegTree) build(p, l, r int) {     if l == r {         this.segNode[p] = this.baskets[l]         return     }     mid := (l + r) >> 1     this.build(p<<1, l, mid)     this.build(p<<1|1, mid+1, r)     this.segNode[p] = max(this.segNode[p<<1], this.segNode[p<<1|1]) } func (this *SegTree) query(p, l, r, ql, qr int) int {     if ql > r || qr < l {         return INT_MIN     }     if ql <= l && r <= qr {         return this.segNode[p]     }     mid := (l + r) >> 1     return max(this.query(p<<1, l, mid, ql, qr),         this.query(p<<1|1, mid+1, r, ql, qr)) } func (this *SegTree) update(p, l, r, pos, val int) {     if l == r {         this.segNode[p] = val         return     }     mid := (l + r) >> 1     if pos <= mid {         this.update(p<<1, l, mid, pos, val)     } else {         this.update(p<<1|1, mid+1, r, pos, val)     }     this.segNode[p] = max(this.segNode[p<<1], this.segNode[p<<1|1]) } func numOfUnplacedFruits(fruits []int, baskets []int)int {     m := len(baskets)     if m == 0 {         returnlen(fruits)     }     tree := SegTree{         segNode: make([]int, 4*m+7),         baskets: baskets,     }     tree.build(1, 0, m-1)     count := 0     for i := 0; i < len(fruits); i++ {         l, r, res := 0, m-1, -1         for l <= r {             mid := (l + r) >> 1             if tree.query(1, 0, m-1, 0, mid) >= fruits[i] {                 res = mid                 r = mid - 1             } else {                 l = mid + 1             }         }         if res != -1 && tree.baskets[res] >= fruits[i] {             tree.update(1, 0, m-1, res, INT_MIN)         } else {             count++         }     }     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-*- import sys INT_MIN = -2**31 class SegTree:     def __init__(self, baskets):         self.baskets = baskets         self.n = len(baskets)         self.seg = [INT_MIN] * (4 * self.n + 7)         if self.n > 0:             self.build(1, 0, self.n - 1)     def build(self, p, l, r):         if l == r:             self.seg[p] = self.baskets[l]             return         mid = (l + r) // 2         self.build(p * 2, l, mid)         self.build(p * 2 + 1, mid + 1, r)         self.seg[p] = max(self.seg[p * 2], self.seg[p * 2 + 1])     def query(self, p, l, r, ql, qr):         if ql > r or qr < l:             return INT_MIN         if ql <= l and r <= qr:             return self.seg[p]         mid = (l + r) // 2         return max(self.query(p * 2, l, mid, ql, qr),                    self.query(p * 2 + 1, mid + 1, r, ql, qr))     def update(self, p, l, r, pos, val):         if l == r:             self.seg[p] = val             return         mid = (l + r) // 2         if pos <= mid:             self.update(p * 2, l, mid, pos, val)         else:             self.update(p * 2 + 1, mid + 1, r, pos, val)         self.seg[p] = max(self.seg[p * 2], self.seg[p * 2 + 1]) def numOfUnplacedFruits(fruits, baskets):     m = len(baskets)     if m == 0:         returnlen(fruits)     tree = SegTree(baskets)     count = 0     for f in fruits:         l, r, res = 0, m - 1, -1         # 在前缀 [0, mid] 上二分查找第一个有足够容量的位置         while l <= r:             mid = (l + r) // 2             if tree.query(1, 0, m - 1, 0, mid) >= f:                 res = mid                 r = mid - 1             else:                 l = mid + 1         if res != -1 and tree.baskets[res] >= f:             # 标记该篮子为已用（在线段树中设为很小的值）             tree.update(1, 0, m - 1, res, INT_MIN)         else:             count += 1     return count if __name__ == "__main__":     fruits = [4, 2, 5]     baskets = [3, 5, 4]     print(numOfUnplacedFruits(fruits, baskets))