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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:06:45 2023-09-13 11:06:45 Updated    

给你一个长度为 偶数 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 <= 105
  • 1 <= nums[i] <= limit <= 105
  • n 是偶数。

假设 res[x] 表示的是，nums[i] + nums[n - 1 - i] 为 x 的时候，需要多少次操作。

我们只需要计算出所有的 x 对应的 res[x], 取最小值就好了。

根据题意，nums[i] + nums[n - 1 - i] 最小是 2，即将两个数都修改为 1；最大是 2 * limit，即将两个数都修改成 limit。

所以，res[x] 中 x 的取值范围是 [2, 2 * limit]。我们用一个 res[2 * limit + 1] 的数组就好。


关键是，如何求出每一个 res[x] 位置的值，即修改后互补的数字和为 x，需要多少操作？

为了叙述方便，假设 nums[i] 为 A；nums[n - 1 - i] 为 B。

显然有：

  • 如果修改后两个数字的和是 A + B，我们使用的操作数是 0 (没有修改));

  • 否则的话，如果修改后两个数字和在 [1 + min(A, B), limit + max(A, B)] 的范围，我们使用的操作数是 1 (只需要修改 A 或者 B 就好);

  • 否则的话，如果修改后两个数字和在 [2, 2 * limit] 的范围，我们使用的操作数是 ``2`(两个数字都要修改));


所以，我们的算法是遍历每一组 nums[i] 和 nums[n - 1 - i]，然后：

  • 先将 [2, 2 * limit] 的范围需要的操作数 + 2；

  • 之后，将 [1 + min(A, B), limit + max(A, B)] 的范围需要的操作数 - 1（即 2 - 1 = 1，操作 1 次）；

  • 之后，将 [A + B] 位置的值再 -1（即 1 - 1 = 0，操作 0 次）。

可以看出，整个过程都是在做区间更新。最后，我们查询每一个位置的值，取最小值就好。


对于这个需求，我们当然可以使用线段树或者树状数组解决，但代码量稍大，且复杂度也是 O(nlogn) 的。

但是仔细观察，我们发现，我们只需要作区间更新，和单点查询。

对于这个需求，有一种非常常规的”数据结构“，叫差分数组，完全满足需求，并且编程极其简单，整体可以在 O(n) 的时间解决。

打上引号，是因为差分数组就是一个数组而已。


简单来说，差分数组 diff[i]，存储的是 res[i] - res[i - 1]；而差分数组 diff[0...i] 的和，就是 res[i] 的值。

大家可以用一个小数据试验一下，很好理解。


如果我们想给 [l, r] 的区间加上一个数字 a, 只需要 diff[l] += a，diff[r + 1] -= a。

这样做，diff[0...i] 的和，就是更新后 res[i] 的值。

依然是，大家可以用一个小数据试验一下，其实很好理解。


有了差分数组这个武器，这个问题就很简单了。

我的参考代码如下（C++）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        
        // 差分数组, diff[0...x] 的和表示最终互补的数字和为 x，需要的操作数
        // 因为差分数组的计算需要更新 r + 1，所以数组的总大小在 limit * 2 + 1 的基础上再 + 1
        vector<int> diff(limit * 2 + 2, 0);

        int n = nums.size();
        for(int i = 0; i < n / 2; i ++){
            int A = nums[i], B = nums[n - 1 - i];

            // [2, 2 * limit] 范围 + 2
            int l = 2, r = 2 * limit;
            diff[l] += 2, diff[r + 1] -= 2;

            // [1 + min(A, B), limit + max(A, B)] 范围 -1
            l = 1 + min(A, B), r = limit + max(A, B);
            diff[l] += -1, diff[r + 1] -= -1;

            // [A + B] 再 -1    
            l = A + B, r = A + B;
            diff[l] += -1, diff[r + 1] -= -1;
        }

        // 依次求和，得到 最终互补的数字和 i 的时候，需要的操作数 sum
        // 取最小值
        int res = n, sum = 0;
        for(int i = 2; i <= 2 * limit; i ++){
            sum += diff[i];
            if(sum < res) res = sum;
        }
        return res;
    }
};

整体时间复杂度是 O(n) 的；空间复杂度也是 O(n) 的。

觉得有帮助请点赞哇！

 Comments
On this page
1674-使数组互补的最少操作次数