给定k个整数集合，找出所选k个元素之间的最小差异
给定k个整数集合，找出所选k个元素之间的最小差异
提问于 2013-04-11 23:51:22
示例: 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
一套二: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。
有什么关于如何处理的建议吗？
回答 1
Stack Overflow用户
发布于 2013-04-11 23:59:54
您可以按如下方式进行操作：
- 使用所有sets
- Initialize
currentBest差的并集构造setUnion，直到setUnion的每个元素的并集 - 的最大和最小元素之间的距离，遍历原始
K集合，并找到大于或等于它的最近元素。您将拥有一组最多为K的编号。找到他们的min和max，并将其与currentBestcurrentBestcompletioncurrentBest进行比较，这样就可以解决您的问题。
如果联合的大小是N，并且您对K集使用有序表示，则此算法将在O(N*K*LogN)时间内找到答案。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15953344
复制相关文章
相似问题
腾讯云开发者
