给定k组整数，找到选择k个元素之间的最小差异

Question

3

我有一个算法问题。给定k个大于0的整数集合（不一定是相同大小），我必须从每个集合中选择一个数字，使得最大值和最小值之间的差异最小。

例子： k=5

集合1:89 45 22 16

集合2:89 34

集合3:37 62 89

集合4:89 96

集合5:89 91 94

答案:从所有集合中选择89，差异为0。

例2(更难) k=5

集合1:12 19 44 52 59 100

集合2:35 60 90 94 98 101

集合3:48 49 57 64 78 90

集合4:15 38 56 90 97

集合5:54 58 59 89 202

答案：选择k个元素为52, 60, 57, 56, 54，差异为60-52=8。

如何解决这个问题？

- user2271058

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

您可以按以下步骤执行：

用所有集合的并构建setUnion
将currentBest差初始化为并集中最小和最大元素之间的距离
对于setUnion的每个元素，遍历原始的K个集合，并找到大于或等于它的最接近的元素。您将得到最多K个数字的集合。找到它们的min和max，并将其与currentBest差进行比较
完成后，currentBest将得到您问题的答案。

如果并集的大小为N，并且您使用有序表示法来表示您的K个集合，此算法将在O(N*K*LogN)时间内找到答案。