1674. 使数组互补的最少操作次数 #

问题描述#

给你一个长度为偶数 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 。

返回使数组互补的最少操作次数。

示例 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 是互补的。
示例 2：
输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。
示例 3：
输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。
提示：

n == nums.length

2 <= n <= 10⁵

1 <= nums[i] <= limit <= 10⁵

n 是偶数。

解题思路#

对于数对 \([a,b],a \le b \le \text{limit}\)，

变化两个数得到的和的范围为 \([2,2\times\text{limit}]\)
只变化 \(b\) 得到的和的范围为 \([a+1,a+\text{limit}]\)
只变化 \(a\) 得到的和的范围为 \([b+1,b+\text{limit}]\)

假设最终使数组互补的最少操作次数时 \(a+b=x\)，

由上面的变化情况可以知道：

当 \(x\in[a+1,b+\text{limit}]\) 时（即合并后两种情况），只用一次操作，但是注意当 \(x=a+b\) 时，操作数为 0.
否则（即 \(x\in [2,2\times\text{limit}],x\notin[a+1,b+\text{limit}]\)），需要两次操作。

所以初始化时将所有数设为 2，然后对于每个数对 \([a,b]\)，将 \([a+1,b+\text{limit}]\) 范围内的数减 1，\(a+b\) 再减 1 即可，最后计算最小的值即可。

很快就能写出下面的代码。

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        A = [n] * (2 * limit + 1)  # n//2 * 2
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            if a > b:
                a, b = b, a
            for j in range(a + 1, b + limit + 1):
                A[j] -= 1
            A[a + b] -= 1
        return min(A[2:])

然后发现超时。

实际上，这样对区间的数加上或减去同一个数的操作，进行多次，最后再获取结果的过程，可以使用序列差分。

from itertools import accumulate
class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        A = [0] * (2 * limit + 2)
        A[0] = n
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            if a > b:
                a, b = b, a
            A[a + 1] -= 1
            A[b + limit + 1] += 1
            A[a + b] -= 1
            A[a + b + 1] += 1
        return min(accumulate(A[:-1]))

1674. 使数组互补的最少操作次数#

问题描述#

解题思路#

1674. 使数组互补的最少操作次数 #