3

我有一个算法问题。给定 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。

关于如何处理的任何建议？

4

1 回答 1

2

你可以这样做：

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

如果联合的大小是N并且您对集合使用有序表示K，则此算法会O(N*K*LogN)及时找到答案。

于 2013-04-11T15:59:54.340 回答