有没有一种方法可以在 O(n) 时间内获取在 k 个已排序数组中组合的元素，这些元素可以使得组合中最小和最大元素之间的差异最小？n 是这些数组中所有元素的总数。
下面是一个例子：
array1 = [11]
array2 = [5,7]
array3 = [6,18]
对于这些数组，以下是所有可能的组合：
comb1 = [11, 5, 6]
comb2 = [11, 7, 6]
comb3 = [11, 5, 18]
comb4 = [11, 7, 18]
6、5、13、11。因此，我应该返回的是comb2，因为该组合的差值最小。将数字一起排序，以及分别对每个数组进行排序：
a: 11
b: 5, 7
c: 6, 18
5, 6, 7, 11, 18
b1 c1 b2 a1 c2
从右侧固定元素开始移除最多可以从左侧移除的内容。在任何时候，仅当该元素是任何一个数组中的最后两个元素之一时，从右侧移除一个元素才会移动左边界。每次更新左边界，如果需要的话，继续移除最右边的元素。选择最好的区间。（请注意，最外两个元素之间的元素并不重要，我们可以选择每个数组中的任何一个作为代表。）
排序后滑动窗口迭代的复杂度为O（n），因为对于排序数组，累计左边界更新为O（n）。
O(n log k)，这已经很不错了，但遗憾的是它不是O(n)。 - le_mO(n)答案。由于你没有提到总体复杂度，我只是加了一条评论而已（实际上，我认为你描述的算法非常优雅）。 - le_mTL;DR 我认为这不可能以O(n)的时间复杂度实现（虽然我无法证明），因此以下是两个O(n*logk)解决方案。
解决方案1：使用大小为k的小根堆，如这里所述。
解决方案2：（我的）
我们需要三个额外的数组，称它们为A、B和C。我们也将输入数组称为“原始数组”。
A 的大小将为 n，并将保持所有原始数组中的元素按排序顺序排列B 也将具有大小 n，并将保留有关数组 A 中元素来源的信息，即来自哪个原始数组元素在 A 中C 将具有大小 k，并且它将包含在过程中从原始数组中看到的元素的最后一个索引（见下文）B中，并将相同原始数组的下一个元素推入堆中）在O(n*logk)时间内创建数组A和B。因此，对于您提供的示例，数组A和B如下所示：A = [5, 6, 7, 11, 18]，B = [1, 2, 1, 0, 2]（5来自第二个原始数组，6来自第三个原始数组等）。k的窗口，其最后一个元素和第一个元素之间的差异最小。这个想法是遍历数组B，直到我们从所有原始数组中“收集”元素 - 这意味着我们找到了一种组合，现在只需检查该组合的第一个和最后一个元素之间的差异即可。现在数组C进入游戏 - 我们将其所有元素初始化为-1，并将C[i]设置为原始数组i中任何元素的最后索引。一旦我们找到第一个包含所有原始数组元素的滑动窗口，我们进一步向右扩展该窗口，并从左缩小，同时保持所有原始数组的代表都在窗口内。因此，算法如下所示：// create arrays A and B, initialize array C
int collected = 0;
int min_idx = 0;
int result = INT_MAX;
for (int i = 0; i < n; ++i) {
bool check_result = false;
if (C[B[i]] == -1) {
++collected;
check_result = true;
}
C[B[i]] = i;
while (min_idx < C[B[min_idx]] && min_idx < i) {
check_result = true;
++min_idx;
}
if (collected < k) continue;
if (check_result && result > (A[i] - A[min_idx]))
result = (A[i] - A[min_idx]);
}
return result;
A = [5, 6, 7, 11, 18]
B = [1, 2, 1, 0, 2]
C = [-1, -1, -1]
i = 0 // state after step 0, we have seen element from array 1
min_idx = 0
C = [-1, 0, -1]
collected = 1
result = INT_MAX
i = 1 // we have seen element from array 2
min_idx = 0
C = [-1, 0, 1]
collected = 2
result = INT_MAX
i = 2 // again element from array 1, increase min_idx
min_idx = 1
C = [-1, 2, 1]
collected = 2
result = INT_MAX
i = 3 // element from array 0, window is full, update result
min_idx = 1
C = [3, 2, 1]
collected = 3
result = 5
i = 4 // again element from array 2, increase min_idx and compare with result -> it is bigger, so don't update result
min_idx = 2
C = [3, 2, 4]
collected = 3
result = 5
O(n*logk)，因为从k个排序数组创建数组A和B需要O(n*logk)，在循环期间，每个n元素最多被检查两次，所以这部分是O(n)，最后O(n*logk + n) = O(n*logk)。如果将原始数组合并为一个数组，则这是您可以获得的最佳效果:
希望这可以帮到您！可以证明，不存在基于比较的k路归并算法，其运行时间为O(n f(k))，其中f增长速度比对数函数慢。
k是否为常数。如果k是某个小的或者常数级别的数字，那么k*n或(logk)*n仍然是O(n)。 - Asad Saeeduddin