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

Question

我有一个算法问题。给定 k 组大于 0 的整数(不一定大小相同)，我必须从每组中选出 k 个数字，以便最大值和最小值之间的差值最小。例子:k=5

设置 1:89 45 22 16

设置 2:89 34

设置 3:37 62 89

设置 4:89 96

设置 5:89 91 94

答案:从所有组差0中选出89。

例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。

关于如何处理有什么建议吗？

Answer 1

您可以按如下方式进行:

• 用所有集合的并集构造setUnion
• 将currentBest差值初始化为并集的最大和最小元素之间的距离
• 对于setUnion的每一个元素，遍历原始的K集合，找到最接近的大于或等于它的元素。您将拥有一组最多 K 个数字。找到它们的 min 和 max，并根据 currentBest 差异进行检查
• 完成后 currentBest 将有您问题的答案。

如果并集的大小是 N 并且您对 K 集使用有序表示，则此算法在 O(N*K *LogN) 时间。