一尘不染

最小差异

algorithm

考虑有数量递增的k列表。从每个列表中选择一个数字,以使输出列表中的最高数字和最低数字之间的差最小:

list 1-1,3,5,9,10
list 2-2,4,6,8
list 3-7,11,12,13

输出应为5,6,7。

从列表1选择5,从列表2选择6,从列表3选择7

由于该列表中最高和最低数字之间的差是2,即7-5,因此请考虑存在k个列表。


阅读 288

收藏
2020-07-28

共1个答案

一尘不染

我可以在中解决此问题O(N*LogK),这N是k个列表中的总数。

1,为每个列表维护一个指针,从0开始。

2,将当前指针作为您选择的数字,更新答案。

3,选择数量最少的一个,并将其增加一个(只要它没有达到列表的末尾),如果可能,请返回步骤2,否则终止。

在第2步和第3步中,使用堆保持最小数量和最大数量,从而将时间从减少O(K)O(LogK)

2020-07-28