最小差 [英] The Minimum difference

问题描述

考虑有在从每个列表越来越order.select一个号码以数字K-列表，使得最高数和最低数目在输出列表之间的差为最小

Consider there are k-lists with numbers in an increasing order.select one number from each list such that the difference between the highest number and lowest number in the output list is minimum

列表1-1​​,3,5,9,10

list 1-1,3,5,9,10

列表2-2,4,6,8

list 2-2,4,6,8

列表3-7,11,12,13

list 3-7,11,12,13

输出应为5,6,7

5从列表-L选择和6从列表-2和7，从列表-3

5 is selected from list-l and 6 from list-2 and 7 from list-3

如在该列表中最高和最低数之间的差是2，其是7-5考虑有k个-列表

as the difference between highest and lowest number in that list is 2 that is 7-5 consider there are k-lists

推荐答案

我可以在解决这个O（N * Logk值），这里ñ 是数字的第k列表的总数。

i can solve this in O(N*LogK), here N is the total number of numbers in the k lists.

1，维持的指针为每个列表，从0开始。

1, maintain a pointer for each list, starting from 0.

2，把当前的指针作为你选择的号码，更新的答案。

2, regard current pointers as the numbers you choose, update the answer.

3，选择一个与最小数目和由一个增加它（只要它没有达到该列表的结尾），如果可能的话，返回到步骤2，否则终止

3, select the one with minimum number and increase it by one(as long as it didn't reach the end of that list), if possible, back to step 2, otherwise terminate.

在步骤2和步骤3，利用堆保持最小数量和最大，这减少 O（K）时间 O（Logk值）。

in step 2, and step 3, use heap to maintain the minimum number and maximum, which reduce the time from O(K) to O(LogK).

这篇关于最小差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！