宁波建站,山东网站建设标准,在线阅读小说网站怎么做,企业网站的缺点题目链接#xff1a;3224. 使差值相等的最少数组改动次数
题目#xff1a;
给你一个长度为 n 的整数数组 nums #xff0c;n 是偶数 #xff0c;同时给你一个整数 k 。
你可以对数组进行一些操作。每次操作中#xff0c;你可以将数组中任一元素替换为 0 到 k 之间的任一…题目链接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 x x一个是 y y y那么改掉其中一个数可以获得的最大差值肯定是把另一个数改成 0 或 k即最大差值 m m a x ( x , k − x , y , k − y ) mmax(x, k-x, y, k-y) mmax(x,k−x,y,k−y)
参考下表
xy差值x0xxkk-x0yykyk-y
改掉两个数那就可以获得从 0 到 k 里的任意差值。
所以对于这一对数来说 X ∣ x − y ∣ X|x-y| X∣x−y∣ 时不需要操作 0 ≤ X ∣ x − y ∣ 0 \leq X |x-y| 0≤X∣x−y∣ 以及 ∣ x − y ∣ X ≤ m |x-y| X \leq m ∣x−y∣X≤m 的时候需要一次操作 X m Xm Xm 的时候需要两次操作。
枚举所有数对用差分数组维护 X X X 的某个取值需要几次操作即可。复杂度 O ( n k ) O(nk) O(nk)。
我们令 d a b s ( n u m s [ i ] − n u m s [ j ] ) dabs(nums[i]-nums[j]) dabs(nums[i]−nums[j])假如最后的这个 0 ≤ X ∣ x − y ∣ 0 \leq X |x-y| 0≤X∣x−y∣那么就可以通过一次操作完成。操作一次能达到的最大差值是多少呢这个就是上面说的肯定是把另一个数改成 0 或 k。即最大差值为 m m a x ( x , k − x , y , k − y ) mmax(x, k-x, y, k-y) mmax(x,k−x,y,k−y)那么就是 ∣ x − y ∣ X ≤ m |x-y| X \leq m ∣x−y∣X≤m 时需要一次操作。剩下就是 X m X m Xm 时需要两次操作。
因为是对区间内的值进行统一的加一个常数的操作如果一个一个操作的话时间复杂度为 O ( n ) O(n) O(n)所以使用了差分数组这样可以将时间复杂度降为 O ( 1 ) O(1) 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
参考13224. 使差值相等的最少数组改动次数 参考2前缀和差分
