最大化最小差异

-2

我们给出N个元素形式的数组A，现在我们必须从N个给定索引中选择K个索引，这样对于任何2个索引i和j，| A [i] -A [j ] |尽可能大。我们需要告诉这个最大值。举个例子：假设N = 5，K = 2，数组为[1,5,3,7,11]，那么这里的答案是10，因为我们可以简单地选择第一个和最后一个位置，并且不同= 11- 1 = 10。例如，设N = 10，K = 3，数组A为[3 9 6 11 15 20 23]，那么这里的答案将为8.因为我们可以选择[3,11,23]或[3， 15,23]。最大化最小差异

现在给定N，K和阵列A，我们需要找到这个最大差异。

我们给出一个1≤N≤10^5和1≤小号≤10^7

来源

2015-03-02 user3840069

让我们对数组进行排序。
现在我们可以对答案进行二分查找。
对于一个固定的候选人x，我们可以选择贪婪的元素（遍历排序后的数组，如果可能的话每个元素）。如果我们挑选的元素数量不小于K,x是可行的。否则，它不是。

时间复杂度为O(N * log N + N * log (MAX_ELEMENT - MIN_ELEMENT))

的伪代码：

bool isFeasible(int x): 
    cnt = 1 
    last = a[0] 
    for i <- 1 ... n - 1: 
     if a[i] - last >= x: 
      last = a[i] 
      cnt++ 
    return cnt >= k 

sort(a) 
low = 0 
high = a[n - 1] - a[0] + 1 
while high - low > 1: 
    mid = low + (high - low)/2 
    if isFeasible(mid): 
     low = mid 
    else 
     high = mid 
print(low)

来源

2015-03-02 19:04:03 kraskevich

你可以提供算法的伪代码 – user3840069 2015-03-02 19:05:10

@ user3840069我刚刚添加它。 – kraskevich 2015-03-02 19:13:17

为什么是可能的（int x）：因为您没有在任何地方使用x – user3840069 2015-03-02 19:16:15

我认为这可以作为一个动态规划问题进行处理。首先排序A，然后问题是在A中标记K个元素，使得相邻标记项之间的最小差异尽可能大。作为初学者，您始终可以标记第一个和最后一个元素。

从左到右移动，在i = 1..N的每个位置，通过在终止于此位置的子数组中标记i元素，可以获得最大的最小差异。您可以计算终止于此位置的k个物品的最大最小差异，方法是考虑终止于您所处位置左侧每个位置的k-1个物品的最大最小差异。最明显的做法是考虑每个可能的位置，直到您当前正在处理的位置，以最小差异结束一段k-1项目，但您可以在此处执行二进制搜索以加快速度。

一旦你一直工作到右手端，你知道原始问题的最大可能值。如果您需要知道K元素的放置位置，您可以随时记录笔记，以便您可以回溯找出导致此解决方案的所选元素，从右向左工作。

来源

2015-03-02 19:08:41 mcdowella

最大化最小差异

回答

相关问题