最小差異

Question

考慮有增加數量的k列表。請從每個列表一個數，使得輸出列表中的最高數和最低數之間的差異最小：

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

輸出應該是5,6,7。

5從列表-1-選擇並從6列表-2和7從列表-3

如在該列表中最高和最低數之間的差是2是7-5考慮有K-名單。

Answer 1

我可以在O(N*LogK)中解決這個問題，這裏N是k個列表中的總數。

1，保持指針每個列表，從0

2日開始，把當前指針作爲你選擇的號碼，更新了答案。

3，選擇一個最小編號並將其增加1（只要沒有達到該列表的末尾），如果可能，返回步驟2，否則終止。

在步驟2和步驟3中，使用堆保持最小數量和最大值，這將時間從O(K)減少到O(LogK)。