Medium

题目描述

给你两个整数数组 fruits 和 baskets，长度都为 n，其中 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 <= 10^5
  • 1 <= fruits[i], baskets[i] <= 10^9

解题思路

这道题的核心在于模拟水果装篮的过程，关键是找到"最左边的可用篮子"。

思路分析：

  1. 朴素模拟法：对每个水果，从左到右扫描所有篮子，找到第一个容量足够且未使用的篮子。时间复杂度 O(n²)。

  2. 优化方法 - 有序集合：使用有序集合（如 set）来维护可用篮子的索引，按篮子容量排序。对每个水果，使用二分查找找到容量足够的最小篮子，然后在相同容量的篮子中选择索引最小的。

  3. 最优解法 - 线段树 + 排序：

    • 将篮子按 (capacity, index) 排序
    • 使用线段树维护原始索引的最小值
    • 对每个水果，二分查找第一个容量足够的篮子范围
    • 在该范围内查询原始索引最小的篮子
    • 找到后将该位置标记为已使用（设为无穷大）

由于题目规模较大（n ≤ 10⁵），推荐使用有序集合的解法，既高效又相对简单。线段树解法虽然理论上更优，但实现复杂度较高。

推荐解法：使用有序集合 + 二分查找，时间复杂度 O(n log n)。

代码实现

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = fruits.size();
        
        // 创建篮子的 (容量, 索引) 对
        vector<pair<int, int>> basket_pairs;
        for (int i = 0; i < n; i++) {
            basket_pairs.push_back({baskets[i], i});
        }
        
        // 按容量排序，容量相同时按索引排序
        sort(basket_pairs.begin(), basket_pairs.end());
        
        // 使用 set 维护可用篮子的索引
        set<int> available;
        for (int i = 0; i < n; i++) {
            available.insert(i);
        }
        
        int unplaced = 0;
        
        for (int fruit : fruits) {
            // 二分查找第一个容量 >= fruit 的篮子
            auto it = lower_bound(basket_pairs.begin(), basket_pairs.end(), 
                                make_pair(fruit, 0));
            
            int best_idx = -1;
            
            // 在容量足够的篮子中找到索引最小的可用篮子
            for (auto iter = it; iter != basket_pairs.end(); iter++) {
                int idx = iter->second;
                if (available.count(idx)) {
                    if (best_idx == -1 || idx < best_idx) {
                        best_idx = idx;
                    }
                }
                // 如果容量变大了，且已找到合适篮子，可以提前退出
                if (best_idx != -1 && iter->first > fruit) {
                    break;
                }
            }
            
            if (best_idx != -1) {
                available.erase(best_idx);
            } else {
                unplaced++;
            }
        }
        
        return unplaced;
    }
};

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        
        # 创建篮子的 (容量, 索引) 对并排序
        basket_pairs = [(baskets[i], i) for i in range(n)]
        basket_pairs.sort()
        
        # 使用 set 维护可用篮子的索引
        available = set(range(n))
        
        unplaced = 0
        
        for fruit in fruits:
            # 二分查找第一个容量 >= fruit 的篮子
            left, right = 0, n
            while left < right:
                mid = (left + right) // 2
                if basket_pairs[mid][0] >= fruit:
                    right = mid
                else:
                    left = mid + 1
            
            best_idx = -1
            
            # 在容量足够的篮子中找到索引最小的可用篮子
            for i in range(left, n):
                capacity, idx = basket_pairs[i]
                if idx in available:
                    if best_idx == -1 or idx < best_idx:
                        best_idx = idx
                # 如果容量变大了，且已找到合适篮子，可以提前退出
                if best_idx != -1 and capacity > fruit:
                    break
            
            if best_idx != -1:
                available.remove(best_idx)
            else:
                unplaced += 1
        
        return unplaced

public class Solution {
    public int NumOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.Length;
        
        // 创建篮子的 (容量, 索引) 对
        var basketPairs = new List<(int capacity, int index)>();
        for (int i = 0; i < n; i++) {
            basketPairs.Add((baskets[i], i));
        }
        
        // 按容量排序，容量相同时按索引排序
        basketPairs.Sort((a, b) => a.capacity == b.capacity ? a.index.CompareTo(b.index) : a.capacity.CompareTo(b.capacity));
        
        // 使用 HashSet 维护可用篮子的索引
        var available = new HashSet<int>();
        for (int i = 0; i < n; i++) {
            available.Add(i);
        }
        
        int unplaced = 0;
        
        foreach (int fruit in fruits) {
            // 二分查找第一个容量 >= fruit 的篮子
            int left = 0, right = n;
            while (left < right) {
                int mid = (left + right) / 2;
                if (basketPairs[mid].capacity >= fruit) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            
            int bestIdx = -1;
            
            // 在容量足够的篮子中找到索引最小的可用篮子
            for (int i = left; i < n; i++) {
                var (capacity, idx) = basketPairs[i];
                if (available.Contains(idx)) {
                    if (bestIdx == -1 || idx < bestIdx) {
                        bestIdx = idx;
                    }
                }
                // 如果容量变大了，且已找到合适篮子，可以提前退出
                if (bestIdx != -1 && capacity > fruit) {
                    break;
                }
            }
            
            if (bestIdx != -1) {
                available.Remove(bestIdx);
            } else {
                unplaced++;
            }
        }
        
        return unplaced;
    }
}

var numOfUnplacedFruits = function(fruits, baskets) {
    const n = fruits.length;
    
    // 创建篮子的 [容量, 索引] 对并排序
    const basketPairs = [];
    for (let i = 0; i < n; i++) {
        basketPairs.push([baskets[i], i]);
    }
    basketPairs.sort((a, b) => a[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² log n)排序 O(n log n)，每个水果需要二分查找 O(log n) 和线性搜索 O(n)，总体 O(n² log n)
空间复杂度O(n)存储篮子对和可用索引集合

相关题目