leetcode 3224. 使差值相等的最少数组改动次数

题目链接：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：前缀和&差分