文章/答案/技术大牛

发布

社区首页 >问答首页 >从大小为N的数组中选择K元素，这样子数组中的最小元素和最大元素之间的差异最小。

问从大小为N的数组中选择K元素，这样子数组中的最小元素和最大元素之间的差异最小。
EN

Stack Overflow用户

提问于 2013-10-21 16:35:06

回答 1查看 959关注 0票数 2

如何从数组中选择K元素，使子数组中的最小元素和最大元素之间的差异最小。

示例:给定数组

     100 200 20 10 30 32 35 50 60 28 18
     k=4

各种可能的结果

    10 18 20 28
    max-min = 28-10 = 18

    28 30 32 35
    max-min = 35-28 = 7

等。

  So, we will select [28 30 32 35] as the subarray

回答已采纳

发布于 2013-10-21 16:48:15

让数组是A1.N.排序。然后选择子阵ai，ai + 1，…，ai +K-1，i= 1，…，N+ 1，这样ai +K-1-ai是极小的。你可以在线性时间内做到这一点。由于排序采用O(nlogn)，算法的总执行时间为O(nlogn)

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/19500017

复制

相似问题

问从大小为N的数组中选择K元素，这样子数组中的最小元素和最大元素之间的差异最小。EN