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

ha 发布于 2019-03-09 c 最后更新 2019-03-09 14:31 0 浏览

我有一个算法问题。给定k个> 0的整数(它们的大小并不一定相同),我必须从每个集合中挑选一个k个数字,以便最大值和最小值之间的差值最小。 例: 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。 有关如何处理的任何建议?

已邀请:

et_qui

赞同来自:

你可以这样做:

  • 使用所有集合的联合构建setUnion
  • currentBest差异初始化为联盟中最大和最小元素之间的距离
  • 对于setUnion的每个元素,请浏览原始的K集,并找到大于或等于它的最接近元素。您将拥有一组最多K个数字。找到他们的minmax,并根据currentBest差异进行检查
  • 完成后,currentBest将解决您的问题。
如果联合的大小为N,并且您对K集使用了有序表示,则此算法会在O(N*K*LogN)时间内找到答案。