algorithm - 找到所有可能的数字集的最大值和最小值之间的最小差异

Question

有 n 个数组，每个数组的大小为 k。

a0[0],a0[1],......a0[k-1]
a1[0],a1[1],......a1[k-1]
.
.
.
an-1[0],an-1[1], .... an-1[k-1]

完全没有重复，所有的数组都是有序的。

现在，通过从每个数组中随机取任意值来构建大小为 n 的集合。例如，一个这样的集合可以是 {a0[0],a1[3],a2[2],.... an-1[k-1]}。

我的目标是在所有可能的集合中找出最小和最大元素，使得最小和最大之间的差异最小。

示例 (k=3,n=3)

[3 7 11]
[1 12 15]
[4 19 21]

所以数学上会有 27 个这样的集合

(3 1 4) (3 12 4) (3 15 4)
(3 1 19) (3 12 19) (3 15 19)
(3 1 21) (3 12 21) (3 15 21)

(7 1 4) (7 12 4) (7 15 4)
(7 1 19) (7 12 19) (7 15 19)
(7 1 21) (7 12 21) (7 15 21)

(11 1 4) (7 12 4) (11 15 4)
(11 1 19) (7 12 19) (11 15 19)
(11 1 21) (7 12 21) (11 15 21)

计算所有这些集合的最小值和最大值后，我们可以得出结论，(3 1 4) 是最小值 (1) 和最大值 (4) 之间的差值是全局最小值或最低值的集合。

因此我们将输出 3 作为全局最小差，对应的对为 (3 4)。如果有多个全局最小值，则将它们全部打印出来。请建议具有更好时间和空间复杂度的算法。我们不能采用蛮力方法。

Answer 1

如果我没理解错的话，您想找到其元素内最大差异在全局上最小的集合。 (我将其称为集合的范围)

从 k 个集合开始，每个集合最初都包含第一个数组中的一个元素。对于每个集合，最小值和最大值将等于元素本身。对于您的示例，这将是 {3}、{7} 和 {11}。

然后您转到第二个数组。对于每个集合，您必须从该数组中选择一个元素来最小化新范围。理想情况下，您会选择一个不会增加范围的元素(但现在不可能)。如果那不可能，请选择可以在两个方向(加号和减号)上扩展您的组合的元素。对于会给您 {1-3}、{3-12}、{1-7}、{7-12}、{1-11} 和 {11-12} 的示例。从这些 2k 集合中，您可以删除重叠的集合。例如，与集合 {1-3} 相比，集合 {1-7} 的范围总是更大或相等。您不需要调查 {1-7} 集。您最终得到集合 {1-3} 和 {11-12}。

转到第三个数组，再次选择尽可能小地扩展每个集合范围的元素。您最终得到 {1-4}、{11-19} 和 {4-12}。然后只选择具有最低范围的那个。