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 是偶数。

解法

方法一：差分数组

思考

要把每对 \(\textit{nums}[i]+\textit{nums}[n-1-i]\) 都变成同一个和 \(s\)，每次把一个数改到 \([1,\textit{limit}]\)。\(n\) 与 \(\textit{limit}\) 都可达 \(10^5\)，不能对每个 \(s\) 再扫一遍数对。

一对 \((x,y)\)（\(x\le y\)）对 \(s\) 的代价在若干区间上分别是 \(2\)、\(1\)、\(0\)、\(1\)、\(2\)，用差分数组把这些区间更新叠在 \([2,2\cdot\textit{limit}]\) 上。

前缀和后取最小即最少修改次数。

假设最终的数组中，数对 \(\textit{nums}[i]\) 和 \(\textit{nums}[n-i-1]\) 的和为 \(s\)。

我们不妨设 \(x\) 为 \(\textit{nums}[i]\) 和 \(\textit{nums}[n-i-1]\) 的较小值，设 \(y\) 为 \(\textit{nums}[i]\) 和 \(\textit{nums}[n-i-1]\) 的较大值。

对于每一对数，我们有以下几种情况：

如果不需要替换，那么 \(x + y = s\)。
如果替换一次，那么 \(x + 1 \le s \le y + \textit{limit}\)。
如果替换两次，那么 \(2 \le s \le x\) 或 \(y + \textit{limit} + 1 \le s \le 2 \times \textit{limit}\)。

即：

在 \([2,..x]\) 范围内，需要替换 \(2\) 次。
在 \([x+1,..x+y-1]\) 范围内，需要替换 \(1\) 次。
在 \([x+y]\) 时，不需要替换。
在 \([x+y+1,..y + \textit{limit}]\) 范围内，需要替换 \(1\) 次。
在 \([y + \textit{limit} + 1,..2 \times \textit{limit}]\) 范围内，需要替换 \(2\) 次。

我们枚举每一个数对，利用差分数组，更新每个数对在不同区间范围内的替换次数。

最后，我们求出下标 \(2\) 到 \(2 \times \textit{limit}\) 的前缀和中的最小值，即为最少的替换次数。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。

相似题目：

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

Python3JavaC++GoTypeScript

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        d = [0] * (2 * limit + 2)
        n = len(nums)
        for i in range(n // 2):
            x, y = nums[i], nums[-i - 1]
            if x > y:
                x, y = y, x
            d[2] += 2
            d[x + 1] -= 2
            d[x + 1] += 1
            d[x + y] -= 1
            d[x + y + 1] += 1
            d[y + limit + 1] -= 1
            d[y + limit + 1] += 2
        return min(accumulate(d[2:]))

class Solution {
    public int minMoves(int[] nums, int limit) {
        int[] d = new int[2 * limit + 2];
        int n = nums.length;
        for (int i = 0; i < n / 2; ++i) {
            int x = Math.min(nums[i], nums[n - i - 1]);
            int y = Math.max(nums[i], nums[n - i - 1]);
            d[2] += 2;
            d[x + 1] -= 2;
            d[x + 1] += 1;
            d[x + y] -= 1;
            d[x + y + 1] += 1;
            d[y + limit + 1] -= 1;
            d[y + limit + 1] += 2;
        }
        int ans = n;
        for (int i = 2, s = 0; i < d.length; ++i) {
            s += d[i];
            ans = Math.min(ans, s);
        }
        return ans;
    }
}

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        int d[limit * 2 + 2];
        memset(d, 0, sizeof(d));
        for (int i = 0; i < n / 2; ++i) {
            int x = nums[i], y = nums[n - i - 1];
            if (x > y) {
                swap(x, y);
            }
            d[2] += 2;
            d[x + 1] -= 2;
            d[x + 1] += 1;
            d[x + y] -= 1;
            d[x + y + 1] += 1;
            d[y + limit + 1] -= 1;
            d[y + limit + 1] += 2;
        }
        int ans = n;
        for (int i = 2, s = 0; i <= limit * 2; ++i) {
            s += d[i];
            ans = min(ans, s);
        }
        return ans;
    }
};

func minMoves(nums []int, limit int) int {
    n := len(nums)
    d := make([]int, 2*limit+2)
    for i := 0; i < n/2; i++ {
        x, y := nums[i], nums[n-1-i]
        if x > y {
            x, y = y, x
        }
        d[2] += 2
        d[x+1] -= 2
        d[x+1] += 1
        d[x+y] -= 1
        d[x+y+1] += 1
        d[y+limit+1] -= 1
        d[y+limit+1] += 2
    }
    ans, s := n, 0
    for _, x := range d[2:] {
        s += x
        ans = min(ans, s)
    }
    return ans
}

function minMoves(nums: number[], limit: number): number {
    const n = nums.length;
    const d: number[] = Array(limit * 2 + 2).fill(0);
    for (let i = 0; i < n >> 1; ++i) {
        const x = Math.min(nums[i], nums[n - 1 - i]);
        const y = Math.max(nums[i], nums[n - 1 - i]);
        d[2] += 2;
        d[x + 1] -= 2;
        d[x + 1] += 1;
        d[x + y] -= 1;
        d[x + y + 1] += 1;
        d[y + limit + 1] -= 1;
        d[y + limit + 1] += 2;
    }
    let ans = n;
    let s = 0;
    for (let i = 2; i < d.length; ++i) {
        s += d[i];
        ans = Math.min(ans, s);
    }
    return ans;
}

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

题目描述

解法

方法一：差分数组

评论