algorithm - 从 N 个数组中各取 1 个元素后最小化 max - min

Question

给定 n 个排序的数组，通过从每个数组中选择一个数字来创建一个新数组，使得新数组中数字的最大值和最小值之间的差异最小。

n=3 输入数组示例:

A = {4, 10, 15}
B = {1, 13, 29}
C = {5, 14, 28}

在这种情况下，答案是从数组 A 中选择 15，从数组 B 中选择 13，从数组 C 中选择 14，因为max[{15, 13, 14}] - min[{15, 13, 14}] = 15 - 13 = 2 并且没有其他组合的最大最小差值低于2.

什么是最有效的算法？

Answer 1

让，A1，A2，... An 是 n 个数组。
假设所有数组都已排序，如果没有，我们可以单独对它们进行排序。

S = [ A1[0], A2[0],...An[0] ]
minSpread = max{S} - min{S}
Iterate i = 1 to L (where L is length of shortest array)
   Remove min{S} from S.
   Insert Ak[i] in S. (where Ak is the kth array from which a value was removed in previous step.)
   minSpread = min(minSpread, max{S} - min{S});

因为我们必须最小化传播(最大-最小)，所以我们唯一的选择是通过删除当前最小值来“向上”挤压最小值。

计算复杂度为 O(N) + O(N*L*logN)，其中 N 为否。数组的长度，L 是最短数组的长度。

这是显示搜索结果时的常见问题。当我们必须显示包含所有给定搜索词的页面摘录的最小可能窗口时。
这里，A1[] A2[]... An[] 包含单词 say-W1, W2... Wn 出现的索引。

编辑:

尼莫:你说得对。证明有点牵扯。您提供的链接尝试了类似的解决方案。我能补充的是:

考虑事实:
1. 我们必须只维护每个数组中的一个元素。
2.数组全部按升序排列。
因此，帮助我们立即丢弃许多组合，与生成所有组合相比，可以在更好的时间内完成。有关详细信息，请访问“Nemo”提供的链接。

并且，通过按照建议维护一个最小堆，可以将复杂度降低到 O(N) + O(N*L*logN)。
其中，N为编号。数组的长度，L 是最短数组的长度。