给定一个大小为 K 的 N 个数组。这 N 个数组中的每一个 K 个元素都是排序的，这些 N*K 元素中的每一个都是唯一的。从 N 个元素的选定子集中，从 N 个数组中的每个数组中选择一个元素。减去最小和最大元素。现在，这
差异应该是最小的。希望问题很清楚:) :)
样本:
N=3, K=3
N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100
在这里，如果选择 16、17、15.. 我们得到的最小差异为
17-15=2。
请您参考如下方法:
我可以想到 O(N*K*N)(在 zivo 正确指出后编辑，现在不是一个好的解决方案:() 解决方案。
1. 取 N 指针最初指向 N 个数组中的每一个的初始元素。
6, 16, 67
^
11,17,68
^
10, 15, 100
^
2.找出当前指针O(k)(6和11)中的最高和最低元素，并找出它们之间的差异。(5)
3. 将该数组中指向最低元素的指针加 1。
6, 16, 67
^
11,17,68
^
10, 15, 100 (difference:5)
^
4. 不断重复第 2 步和第 3 步，并存储最小差值。
6, 16, 67
^
11,17,68
^
10,15,100 (difference:5)
^
6, 16, 67
^
11,17,68
^
10,15,100 (difference:2)
^
以上将是所需的解决方案。
6, 16, 67
^
11,17,68
^
10,15,100 (difference:84)
^
6, 16, 67
^
11,17,68
^
10,15,100 (difference:83)
^
等等......
编辑:
它的复杂性可以通过使用堆来降低(正如 Uri 所建议的那样)。我想到了，但遇到了一个问题:每次从堆中提取一个元素时，都必须找出它的数组编号，以便为该数组增加相应的指针。 找到数组编号的有效方法绝对可以将复杂度降低到 O(K*N log(K*N)) .一种天真的方法是使用这样的数据结构
Struct
{
int element;
int arraynumer;
}
并重建初始数据，如
6|0,16|0,67|0
11|1,17|1,68|1
10|2,15|2,100|2
最初保留第一列的当前最大值并将指向的元素插入堆中。现在每次提取一个元素时，可以找出它的数组编号，该数组中的指针递增，新指向的元素可以与当前的最大值进行比较，并且可以相应地调整最大值指针。
