最小化最大差异

Question

我正在尝试通过以下方法从 GFG 解决这个 Problem：

class Solution:
    def getMinDiff(self, arr, n, k):
        # code here
        arr.sort()
        min_diff = arr[-1] - arr[0]
        if min_diff <= k:
            return min_diff
        
        min_ele = arr[0] + k
        max_ele = arr[-1] - k
        if min_ele > max_ele:
            min_ele, max_ele = max_ele, min_ele
            
        for i in range(1, n-1):
            curr_min = arr[i] - k
            curr_max = arr[i] + k
            
            if curr_min >= min_ele or curr_max <= max_ele:
                continue
            
            if max_ele - curr_min <= curr_max - min_ele:
                min_ele = curr_min
            else:
                max_ele = curr_max
                
        return min(min_diff, max_ele - min_ele)


if __name__ == '__main__':
    tc = int(input())
    while tc > 0:
        k = int(input())
        n = int(input())
        arr = list(map(int, input().strip().split()))
        ob = Solution()
        ans = ob.getMinDiff(arr, n, k)
        print(ans)
        tc -= 1

但是我无法通过测试用例：

Input:
4
10
6 1 9 1 1 7 9 5 2 10

Its Correct output is:
5

And my Code's output is:
6

我无法找出我的逻辑或代码中的错误。有人可以建议更正或更好的方法吗？

Answer 1

I'm unable to figure out fault in my logic or code.

根据您当前的逻辑，您决定仅根据当前元素来添加或减去 k。但它可能不会产生总体上的最小差异。例如，对于 5，您决定添加 k，结果整个集合的范围为 (5,11)。相反，如果你减去它会产生 (1,6).

Could some suggest corrections or better approach?

方法：

对数组进行排序
让我们处理琐碎的情况，if k > (max - min) 然后直接 return max - min。因为将 k 加到 min 和从 max 中减去 k 会产生更大的差异。（准确地说，2 * k + (max - min)）
在所有其他情况下，我们将向最小元素添加 k 并从最大元素中减去 k。数组中应该存在一个索引，我们从添加 k 切换到减去 k。下图显示了开关索引：

(注：图中B可以小于D，A也可以大于C)

现在我们遍历数组和每个索引，如果它是我们确定范围的开关索引。
- 从图中我们可以计算出范围如下
  - 如果 A < C 那么范围将以 A 开始，否则以 C
  - 同样，如果 B > D 那么范围将以 B 结束，否则以 D
所有索引的最小值 range 给出结果

更新代码：

def getMinDiff(self, arr, n, k):
    # code here
    arr.sort()
    min_diff = arr[-1] - arr[0]
    if min_diff <= k:
        return min_diff
    
    for i in range(0, n-1):
        if arr[i + 1] < k :
            continue
        start = min(arr[0] + k, arr[i + 1] - k)
        end = max(arr[-1] - k, arr[i] + k)
        min_diff = min(min_diff, end - start)
            
    return min_diff

解释：

在for循环中，我们确定每个元素的switch索引范围如下
- 开始：从图中的最小值 A 和 C 开始。这里 A 是 arr[0] + k 而 C 将是 next element - k 即。 arr[ i + 1 ] - k
- 结束：B 和 D 的最大值。 B 是 current element + k，即 arr[i] + k 和 D 将是 arr[-1] - k

最小化最大差异

Minimize the maximum difference

python

arrays

greedy