Chocolate Distribution Problem
你有一些巧克力包，packets[i] 表示第 i 包巧克力的数量。m 名学生每人恰好拿一包，因此会发出 m 包不同的巧克力。挑选这些巧克力包，使发出的最多巧克力包与最少巧克力包之间的差尽可能小。
编写一个名为 minDifference 的函数，返回这个可能的最小差值。
函数
- packetsinteger-array
- 每包巧克力的数量
- minteger
- 学生人数，每人拿到一包
- 返回值integer
- 分发的最大数据包和最小数据包之间可能的最小差值
约束条件
2 ≤ m ≤ packets.length ≤ 1041 ≤ packets[i] ≤ 105- 两个包装袋可以装相同数量的巧克力。
示例
- 输入
- packets = [9, 3, 15, 7, 11, 4]m = 3
- 输出
- 4
- 解释
- 排序后，数据包依次为 3、4、7、9、11 和 15。3、4、7 和 7、9、11 的差值都是
4，没有三个数据包彼此更接近。
- 输入
- packets = [20, 5, 18, 6, 19]m = 2
- 输出
- 1
- 解释
- 5 和 6 相差 1，18 和 19 相差 1，19 和 20 也相差 1。没有两个数据包相等，因此没有任何一对的差值能小于 1。
- 输入
- packets = [8, 1, 5]m = 3
- 输出
- 7
- 解释
- 有 3 名学生和 3 个包裹，所以每个包裹都会被送出，差值是
8 - 1 = 7。
提示
逐个打开提示，每个都会多透露一点。
假设你已经知道要分发的最小数据包。还应该把哪些其他数据包和它一起分发？
固定最小的数据包后，按大小顺序分发紧随其后的
m-1个数据包：更大的数据包只会拉大差距。按排序后的顺序，这些数据包彼此相邻。对数据包排序。每组连续的
m个相邻数据包构成一个窗口，差值等于最后一个数据包减去第一个数据包。从左向右滑动窗口，并保留最小的差值。
题解
尝试每一组由 m 个数据包组成的组合，速度太慢了。最佳选择总是排序后彼此相邻的 m 个数据包。因此，先排序一次，然后只需遍历一遍，找出任意连续 m 个数据包之间的最小差值。
修复最小的数据包
结果正确，但无法在最大的测试中运行完毕
思路
把你发放的最小包设为 low。为了让最大的包尽可能小，选出至少有 low 个的最小的 m-1 个包。这样，差值就是至少有 low 个的第 m 小的包减去 low。把每个包都试作 low，跳过数量少于 m 个且大小不小于它的情况，并保留最小的差值。
每种 n 种选择都会筛选并排序最多 n 个包：O(n² log n)。当 n = 10^4 且有不同大小时，仅排序就会进行约 6 × 10^8 次比较。
算法
- 将
best初始化为一个不可能被任何答案超过的值。 - 对于每个
low数据包，收集所有至少有low个巧克力的数据包，并将它们排序。 - 如果这样的数据包至少有
m个，那么第m小的数量减去low就是一个候选值。 - 将最小的候选值保存在
best中，并返回它。
def minDifference(packets, m):
best = max(packets) - min(packets) # no gap can be wider than this
for low in packets:
# The packets that could go out alongside low, smallest first (low is one of them).
bigger = sorted(x for x in packets if x >= low)
if len(bigger) >= m:
best = min(best, bigger[m - 1] - low)
return best对 m 个数据包排序并滑动窗口
思路
按升序排列后，窗口 sizes[i..i+m-1] 中最小的数据包在最前面，最大的数据包在最后面，因此它们的差是 sizes[i+m-1] - sizes[i]。
最优选择总是可以是一个窗口。如果选择跳过了一个位于最小和最大数据包之间的数据包，就把它换进来，替换掉最大的数据包。最小值保持不变，最大值只会变小，因此差值不会增大。重复这个过程，直到没有间隔为止。
在第一个示例中，包含 3 个数据包的窗口对应的差值分别为 4、5、4 和 6，因此答案是 4。排序的时间复杂度是 O(n log n)，滑动窗口的时间复杂度是 O(n)。
算法
- 将数据包按升序排序到
sizes中。 - 将
best设为sizes[m-1] - sizes[0]，也就是第一个窗口。 - 对于从 1 到
n-m的每个起始位置i，将sizes[i+m-1] - sizes[i]与best比较，并保留较小值。 - 返回
best。
def minDifference(packets, m):
sizes = sorted(packets)
best = sizes[m - 1] - sizes[0]
# The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
for i in range(1, len(sizes) - m + 1):
best = min(best, sizes[i + m - 1] - sizes[i])
return best
易错点和边界情况
- 将窗口结束位置设为
i+m而不是i+m-1，这样会包含m+1个包。 - 提前停止一个窗口。起始位置从 0 到
n-m，包含n-m。对于[1, 10, 20, 21]，当m = 2时，使用i < n-m作为循环条件会漏掉唯一为 1 的差值。 - 跳过排序。在
[9, 3, 15, 7, 11, 4]中，前 3 个包的差值是 12，而答案是 4。 - 只测量第一个窗口。最小的
m个包是一种选择，但最佳分组可能从任意位置开始。 - 将数字按文本排序。在 JavaScript 中，不带比较器的
sort()会把100000排在9前面。
常见问题3
巧克力分配问题的时间复杂度是多少？
排序需要 O(n log n)，滑动包含 m 个数据包的窗口需要 O(n)，因此总复杂度为 O(n log n)。额外空间用于存储排序后的副本时为 O(n)；如果直接对输入进行原地排序，则除排序本身所需空间外，额外空间为 O(1)。
巧克力分配问题是滑动窗口问题吗？
是的，这是一个覆盖已排序数据包的固定大小窗口。与运行和窗口不同，窗口移动时无需更新任何内容：每个窗口的差值只需用最后一个数据包减去第一个数据包。
巧克力分配问题能否在不排序的情况下解决？
这里的大小最多为 10^5，因此计数排序可以在 O(n + 10^5) 时间内将它们排序，后续推导也同样成立。对于没有上限的大小，仅靠比较无法将时间复杂度降到 O(n log n) 以下：当 m = 2 时，只有两个数据包相等，答案才恰好为 0；而在最坏情况下，检测重复项需要进行同样多次比较。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def minDifference(packets, m):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
packets = [9, 3, 15, 7, 11, 4] m = 3
预期输出
4