O(n)时间最小的生成窗口组合k个排序数组中的元素

Question

有没有办法及时得到排序数组中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,因为这种组合的差异是最小的.

如果它有帮助,原始数组中的整个值集中没有重复元素.

Answer 1

对数字进行排序，并分别对每个数组进行排序：

a: 11
b: 5, 7
c: 6, 18

5,  6,  7, 11, 18
b1 c1  b2  a1  c2

对于我们做出的不删除外部数字（最右边或最左边）的任何选择，下一个选择序列是明确的。如果我们选择固定(18)，我们可以从左边c2向上。b2但如果我们删除c2，左边界的唯一变化是在c数组本身内。

从我们可以从左侧删除的最多的固定最右侧元素开始。在任何时候，如果该元素是任何一个数组中的最后两个元素之一，则从右侧删除元素只会移动左边界。继续删除最右边的元素，每次根据需要更新左边界。选择最明显的间隔。（注意，外面两个元素之间的元素并不重要，我们可以从每个数组中选取任意一个作为代表。）

排序后滑动窗口迭代的复杂性是，O(n)因为对于排序数组，累积左边界更新为O(n)。