考虑有数量递增的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个列表。
我可以在中解决此问题O(N*LogK),这N是k个列表中的总数。
O(N*LogK)
N
1,为每个列表维护一个指针,从0开始。
2,将当前指针作为您选择的数字,更新答案。
3,选择数量最少的一个,并将其增加一个(只要它没有达到列表的末尾),如果可能,请返回步骤2,否则终止。
在第2步和第3步中,使用堆保持最小数量和最大数量,从而将时间从减少O(K)到O(LogK)。
O(K)
O(LogK)