題目鏈接：3224. 使差值相等的最少數組改動次數

題目：

給你一個長度為 n 的整數數組 nums ，n 是偶數 ，同時給你一個整數 k 。

你可以對數組進行一些操作。每次操作中，你可以將數組中任一元素替換為 0 到 k 之間的任一整數。

執行完所有操作以后，你需要確保最后得到的數組滿足以下條件：

存在一個整數 X ，滿足對于所有的 (0 <= i < n) 都有 abs(a[i] - a[n - i - 1]) = X 。
請你返回滿足以上條件最少修改次數。

提示：

2 <= n == nums.length <= 105

n 是偶數

0 <= nums[i] <= k <= 105

題解：

方法一：暴力解法

直接枚舉 X 的取值，然后計算每個枚舉值對應所需修改的次數，然后選出里面最小的即可。

這里的第一個問題是 X 的取值范圍如何確定。從題目的提示內容可知數組中的數在 0-k 之間，又因為 數組中的數字可以修改為 0-k之間的任意數，所以直接上 X 的取值范圍為 0 <= X <= k

第二個問題是如何讓數組中對稱位置的兩個數字在修改之后差值為 X，這里直接枚舉兩個數字可以修改的所有值，如果修改前后的數值不同則記錄為1次修改，否則不記錄為修改。

代碼實現：

def minChanges(nums, k):n = len(nums)change_count = [0] * (k + 1)# 遍歷前半部分for i in range(n // 2):a, b = nums[i], nums[n - i - 1]temp = [float('inf')] * (k + 1)  # 臨時數組，用于計算當前的最小修改次數# 遍歷每個可能的 Xfor x in range(k + 1):# 當前 |a - b| 與目標 X 的差異for v1 in range(k + 1):  # 枚舉將 a 修改為 v1for v2 in range(k + 1):  # 枚舉將 b 修改為 v2if abs(v1 - v2) == x:  # 如果調整后符合要求cost = (v1 != a) + (v2 != b)  # 計算修改次數temp[x] = min(temp[x], change_count[x] + cost)# 更新最小修改次數change_count = tempreturn min(change_count)

方法二：差分數組

注意到每一對數不會互相影響，所以可以把每一對數分開考慮。
設一對數中，一個是 $x$，一個是 $y$，那么改掉其中一個數可以獲得的最大差值，肯定是把另一個數改成 0 或 k，即最大差值：

$m=max(x,k?x,y,k?y)$

參考下表：

x	y	差值
x	0	x
x	k	k-x
0	y	y
k	y	k-y

改掉兩個數，那就可以獲得從 0 到 k 里的任意差值。

所以對于這一對數來說，$X=|x?y|$ 時不需要操作，$0\le X<|x?y|$ 以及 $|x?y|<X\le m$ 的時候需要一次操作，$X>m$ 的時候需要兩次操作。

枚舉所有數對，用差分數組維護 $X$ 的某個取值需要幾次操作即可。復雜度 $O(n+k)$。

• 我們令 $d=abs(nums[i]?nums[j])$，假如最后的這個$0\le X<|x?y|$，那么就可以通過一次操作完成。
• 操作一次能達到的最大差值是多少呢？這個就是上面說的肯定是把另一個數改成 0 或 k。即最大差值為 $m=max(x,k?x,y,k?y)$，那么就是 $|x?y|<X\le m$ 時需要一次操作。
• 剩下就是 $X>m$ 時需要兩次操作。

因為是對區間內的值進行統一的加一個常數的操作，如果一個一個操作的話時間復雜度為 $O(n)$，所以使用了差分數組，這樣可以將時間復雜度降為 $O(1)$

from typing import Listclass Solution:def minChanges(self, nums: List[int], k: int) -> int:n = len(nums)f = [0] * (k + 2)i, j = 0, n - 1while i < j:d = abs(nums[i] - nums[j])ma = max(nums[i], k - nums[i], nums[j], k - nums[j])# 0 <= x < d 時需要一次操作，如果沒有用差分數組的話就成了 cnt[0]+1,cnt[1]+1,···,cnt[d]+1f[0] += 1f[d] -= 1# d < x <= ma 時需要一次操作f[d + 1] += 1f[ma + 1] -= 1# x > ma 時需要兩次操作f[ma + 1] += 2i += 1j -= 1ans = f[0]for i in range(1, k + 2):f[i] += f[i - 1]ans = min(ans, f[i])return ans

參考1：3224. 使差值相等的最少數組改動次數
參考2：前綴和&差分