给你一个长度为 偶数 n
的整数数组 nums
和一个整数 limit
。
每一次操作,你可以将 nums
中的任何整数替换为 1
到 limit
之间的另一个整数。
如果对于所有下标 i
(下标从 0
开始),nums[i] + nums[n - 1 - i]
都等于同一个数,则数组 nums
是 互补的 。例如,数组 [1,2,3,4]
是互补的,因为对于所有下标 i
,nums[i] + nums[n - 1 - i] = 5
。
返回使数组 互补 的 最少 操作次数。
提示:
n == nums.length
2 <= n <= 105
1 <= nums[i] <= limit <= 10^5
n 是偶数。
示例 1:
输入:nums = [1,2,4,3], limit = 4
输出:1
解释:经过 1 次操作,你可以将数组 nums 变成 [1,2,2,3](加粗元素是变更的数字):
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ,nums[i] + nums[n-1-i] = 4 ,所以 nums 是互补的。
假设我们知道我们最终把所有数变换到同一个数是$x \in [2,2 \times 1e5]$
$nums$数组总共$n$个数,共$n//2$个数对,则将每个数对和 变换到x需要的次数相对于x-1的操作数的变化量d:
$$
d
\begin{cases}
-1, x==min(nums[i],nums[n-i-1])+1 \\\\
-1, x==nums[i]+nums[n-i-1] \\\\
+1, x==nums[i]+nums[n-i-1]+1 \\\\
+1, x==max(nums[i],nums[n-i-1])
\end{cases}
$$
原因是
1.当$x<min(nums[i],nums[n-i-1])+1$时需要两次
2.则$x$取为$min(nums[i],nums[n-i-1])+1$只需要把大的数变为$1$,操作次数为$1$次,相较于$x-1$的次数$-1$,因此$x \in [min(nums[i],nums[n-i-1])+1,nums[i]+nums[i-1])$时需要1次
3.则$x$取为$nums[i]+nums[n-i-1]$不需要操作,操作次数为0次,相较于前一个状态$x-1$需要的次数-1
4.$x \in [nums[i]+nums[n-i-1],max(nums[i],nums[i-1])+limit)$时需要把其中一个数减到num[i]+nums[n-i-1]==x为止,需要1次,相较于前一个状态$x-1$需要的次数+1
5.$x \in [max(nums[i],nums[i-1])+limit,2\times limit]$时需要把两个数都减,直到$num[i]+nums[n-i-1]==x$为止,需要$2$次,相较于前一个状态$x-1$需要的次数+1
答案
由于这是代表变化量的数组$d$–差分数组d,则答案
$$=选择最终相同的数i时最小需要的操作次数=min(\sum_{2}^{i} d[i]) for {~}i \in [2,2*limit]$$
class Solution:
def minMoves(self, nums: List[int], limit: int) -> int:
d = [0]*(limit*2+2)
n = len(nums)
for i in range(n//2):
low = min(nums[i],nums[n-i-1])+1
hi = max(nums[i],nums[n-i-1])+limit
d[low]-=1
d[nums[i]+nums[n-i-1]]-=1
d[nums[i]+nums[n-i-1]+1]+=1
d[hi+1]+=1
res = n
tmp = n
for i in range(2,2*limit+1):
tmp+=d[i]
res = min(res,tmp)
return res