共计 3781 个字符，预计需要花费 10 分钟才能阅读完成。
问题背景：
给你两个长度为
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。
注意：
n == fruits.length == baskets.length
1 <= n <= 105
1 <= fruits[i], baskets[i] <= 109
该题 中数据量较大，直接使用暴力破解的方式遍历每个水果 对所有篮子进行判断 会非常影响效率。所以需要进行优化。因为篮子数较多，每个篮子都有它的容量，因此想到用分块的思想。
将篮子数量进行分块 成组，每组 m 个篮子，维护一个数组 maxV[] 用于存储每组的最大容量
当篮子的最大容量大于等于水果数量时，进入该分组，选择一个最优的篮子 放入该水果。
基本思路
该问题的核心挑战是如何高效地为每个水果找到合适的篮子。暴力解法会 ** 对每个水果遍历所有篮子 **，时间复杂度为 O(n*m)，当 n 和 m 较大时效率低下。平方根分解（SQRT Decomposition）是一种将数据分成块进行处理的优化方法，可以将时间复杂度降低到 O(m√n)。
优化思想
此处进行分组的方式 - 平方根分组
平方根分解的基本思想是：
- 将篮子数组分成若干块，每块大小约为√n
- 为每个块维护一个最大值，用于快速判断该块是否可能有合适的篮子
- 处理每个水果时，先检查各块的最大值，跳过不可能的块
- 在可能的块内遍历篮子，找到第一个符合条件的篮子
实现：
变量定义与初始化
在代码实现中，关键变量的含义如下：
n：篮子的总数量m：每个块的大小，取约√nsection：块的数量，计算为Math.ceil(n/m)篮子总数量 / 每个块大小 得到的就是 分组数也就是块数maxV：数组，存储每个块中的最大篮子容量
Math.ceil() 用于将数字向上舍入到最接近的整数。若参数不是数字类型，将返回 TypeError
初始化结果：
const n = baskets.length; // 篮子数量
const m = Math.floor(Math.sqrt(n)); // 每个块的大小约为√n
const section = Math.ceil(n / m); // 块的数量
let count = 0; // 记录未放置的水果数量
const maxV = new Array(section).fill(0); // 存储每个块的最大容量Math.floor() 是一个用于向下取整的函数，它返回小于或等于给定数字的最大整数
// 遍历篮子
for(let i =0;i<n;i++) {
// 当前篮子所属的块索引
// 每个块包含 m 个篮子，第 i 个篮子除以 m 的整数部分，就是它所在的块索引。const sec = Math.floor(i / m)
// 记录每组的最大容量
maxV[sec] = Math.max(maxV[sec],baskets[i])
}
开始放置水果（遍历水果）
for (fruit of fruits) { let unset = 1 // 表示当前没有被放置，后续的叠加结果作为没有被放置的水果总数 for(let sec= 0;sec<section;sec++) { // 如果 当前分块的最大容量也小于水果量 直接跳过当次遍历 进入下一次遍历 if(maxV[sec] < fruit) {continue} // 可以存放水果 let choose = 0 // 当前块中是否已找到合适的篮子 maxV[sec] = 0 // 放置水果以后 后面会重新计算当前块的最大容量 以保证准确性 // 遍历当前分块 m 就是每个块的长度 for (let i =0;i<m;i++) { const pos = sec * m +i //pos 是当前块内第 i 个篮子在原始数组 baskets 中的索引。// 块 sec 的起始索引是 sec * m（每个块有 m 个元素），加上块内的偏移量 i（0 到 m -1），就是原始数组中的具体位置。// 放入水果 if(pos < n && baskets[pos] >= fruit && !choose) {baskets[pos] =0 // 当前分块 找到合适的篮子 choose =1 } // 在块内有篮子被使用后，及时更新该块的最大可用容量 // // 分块策略中维持“块最大值准确性”的关键步骤 if(pos < n) { //：防止数组越界、// 重新计算当前块的最大篮子容量 maxV[sec] = Math.max(maxV[sec],baskets[pos]) } } // 水果已经放置 unset = 0 break } count +=unset // 记录无法放置的水果 } return count // 返回结果 就是无法被放置的水果种类数完整实现代码 JS 版本
var numOfUnplacedFruits = function(fruits, baskets) { // 将篮子分组，取得每组中最大容量，然后遍历水果 const n = baskets.length const m = Math.floor(Math.sqrt(n)) // ?? 为何是这样的数量 const section = Math.ceil(n/m) // 组数，用 篮子的总数量 / 分组的大小 let count = 0 // 计数 const maxV = new Array(section).fill(0) // 遍历篮子 for(let i =0;i<n;i++) { // 当前篮子所属的块索引 // 每个块包含 m 个篮子，第 i 个篮子除以 m 的整数部分，就是它所在的块索引。const sec = Math.floor(i / m) // 记录每组的最大容量 maxV[sec] = Math.max(maxV[sec],baskets[i]) } // 遍历水果 for(const fruit of fruits) { let unset = 1 // 表示当前没有被放置，后续的叠加结果作为没有被放置的水果总数 // 找到 一个块 最大容量大于水果量 for(let sec= 0;sec<section;sec++) { // 如果 当前分块的最大容量也小于水果量 直接跳过当次遍历 进入下一次遍历 if(maxV[sec] < fruit) {continue} // 可以存放水果 let choose = 0 // 当前块中是否已找到合适的篮子 maxV[sec] = 0 // 重新计算当前块的最大容量 // 遍历当前分块 m 就是每个块的长度 for (let i =0;i<m;i++) { const pos = sec * m +i //pos 是当前块内第 i 个篮子在原始数组 baskets 中的索引。// 块 sec 的起始索引是 sec * m（每个块有 m 个元素），加上块内的偏移量 i（0 到 m -1），就是原始数组中的具体位置。// 放入水果 if(pos < n && baskets[pos] >= fruit && !choose) {baskets[pos] =0 // 当前分块 找到合适的篮子 choose =1 } // 在块内有篮子被使用后，及时更新该块的最大可用容量 // // 分块策略中维持“块最大值准确性”的关键步骤 if(pos < n) { //：防止数组越界、// 重新计算当前块的最大篮子容量 maxV[sec] = Math.max(maxV[sec],baskets[pos]) } } // 水果已经放置 unset = 0 break } // 记录数量 count+=unset } // 返回结果 return count };本题中学到的地方
pos 当前块内第
i个篮子在原始数组baskets中的索引。计算方法为：const pos = sec * m + i // 块
sec的起始索引是sec * m加上第 i 个篮子的偏移量 i符合放置条件的篮子的判断
// 放入水果 if(pos < n && baskets[pos] >= fruit && !choose) {baskets[pos] =0 // 当前分块 找到合适的篮子 choose =1 }
维持分块思想 准确性的 更新机制
// 分块策略中维持“块最大值准确性”的关键步骤
if(pos < n) { //：防止数组越界、// 重新计算当前块的最大篮子容量
maxV[sec] = Math.max(maxV[sec],baskets[pos])
}该方法优势
避免了对每个篮子进行线性遍历，时间复杂度为 O(√n)，适合篮子数量较多的情况下。
