数组中n个元素的最大最小差
数组中n个元素的最大最小差
提问于 2020-04-26 09:03:31
给定数组A和数N。
从数组A中选择N个元素，使这些N个数之间的最小差值最大化。返回最大最小差。
Example1. A= {1,2,4,8,9}，N=3
输出：3(因为{1,4,9}使这3个数字之间的差异最大化。4-1=3，9-4=5)
Example2. A= {4,1,2,8,90,900}，N=4
输出：7
这是一个数据结构课程的问题，我为这个问题奋斗了一整天，我希望有人能帮我解决这个问题。谢谢!
回答 2
Stack Overflow用户
发布于 2020-04-26 10:52:52
- 为N=2排序数组
- 输出的值为0和n为数组的索引(n是数组的长度)，
- 用于N=3 0、n和n/2 (如果n为奇数，则需要检查n/2和n/2+1的哪个更好)，并将数组拆分为2
- 进行N=4，需要检查两个数组的哪个“中间”得到最好的结果。
H19我认为您得到了它，总是将其除以2。H 210G 211
复杂性: n*log(n)用于排序+N(用于检查+拆分)
Stack Overflow用户
发布于 2020-04-26 13:34:09
我们可以有一个简单的具有O(n * log(n) * N)时间复杂度的动态程序，其中n是A中的元素数。假设数组已经排序，让f(i, k)表示k元素的最优解中最大的最小差异，从第一个元素选择到i元素，然后：
f(i, k) ->
max(min(A[i] - A[j], f(j, k - 1)))
for all k - 2 ≤ j < i由于A[i] - A[j]没有增加，f(j, k - 1)也没有随着j的增加而减少，所以较小的值表示一个单峰函数，因此我们可以在每次迭代中二进制搜索最优的j。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61438232
复制相关文章
相似问题
腾讯云开发者
