Leetcode每日一题 —— 1674. 使数组互补的最少操作次数

1674. 使数组互补的最少操作次数 - 力扣（LeetCode）

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[i] <= limit，最终必然可以凑成互补数组，且一对数的和的范围为 2 <= nums[i] + nums[n-i-1] <= limit*2。

设有一对数 <nums[i], nums[n-i-1]>, 且 a 是其中较小的一个，b 是其中较大的一个，要凑成一个和 F (2 <= F <= limit*2)。

分五个情况：

1. 2 <= F < a+1 (操作 2 次)
   • (此时 b 变换为最小值 1，但 a+1 仍然 > F，还要替换 a；注意这种情况不会有 b=1，因为 b=1 就有 a=1, 必然 = F)
2. a+1 <= F < a+b (操作 1 次)
   • (因为 F < a+b, 只需要减小 b 即可)
3. a+b = F (不需要操作)
4. b+a < F <= b+limit (操作 1 次)
   • (类比 case 2，增大 a 即可)
5. b+a < b+limit < F <= limit+limit (操作 2 次)
   • (类比 case 1, 这种情况不会有 a=limit，因为 a=limit 就有 b=limit，必然 = F)

每一对数下五种情况正好是彼此相邻的区间，把数字和转换到不同区间需要不同操作数。

不同数对的这些区间会互相交叠，为了加速统计 nums 中所有数字对的和转换为不同 F 的操作数，就可以用差分数组来实现。

五种情况正好对应差分数组中五个操作数突变点，对每对数字的情况都更新一下差分数组，最终计算差分数组前缀和就能知道让互补和 F 取哪个数对应的操作数最少了。

代码

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        // 因为 1 <= nums[i] <= limit，必然是可以凑成的
        // 两个数的和的范围 2 <= nums[i] + nums[n-i-1] <= limit*2
        // 设有一对数 (nums[i], nums[n-i-1]), a 是较小的一个，b 是较大的一个，要凑成 F，有 2 <= F <= limit*2
        // 
        // case 1: 2 <= F < a+1 (操作 2 次)
        //     (此时 b 变换为最小值 1，但 a+1 仍然 > F，还要替换 a. 注意这种情况不会有 b=1，因为 b=1 就有 a=1, 必然 = F)
        // case 2: a+1 <= F < a+b (操作 1 次)
        //     (因为 F < a+b, 只需要减小 b 即可)
        // case 3: a+b = F (不需要操作)
        // case 4: b+a < F <= b+limit (操作 1 次)
        //     (类比 case 2，增大 a 即可)
        // case 5: b+a < b+limit < F <= limit+limit (操作 2 次)
        //     (类比 case 1, 这种情况不会有 a=limit，因为 a=limit 就有 b=limit，必然 = F)
        //
        // 可以发现 5 种情况正好是彼此相邻的区间，可以用差分数组来加速统计 **nums 所有数字对**转换为不同情况 F 的总操作数

        int n = nums.size();
        // 目标和最大是 2*limit，如果 b 是 limit，我们就需要访问 limit*2 + 1 这个下标
        vector<int> diff(limit*2+2,0);
        for(int i=0;i<(n>>1);i++){
            int a=min(nums[i],nums[n-1-i]);
            int b=max(nums[i],nums[n-1-i]);
            // 接下来看 <a, b> 这一组数，转换为 case 1-5 情况所需要的操作数
            diff[2]+=2; // 垫底情况，转换两次 a+b=2
            diff[a+1]-=1; // 进入 case2，少一次转换
            diff[a+b]-=1; // 进入 case3，再少一次
            diff[a+b+1]+=1; // 进入 case4，多一次
            diff[b+limit+1]+=1; // 进入 case5，多一次
        }
        // 统计每一对转换为每种情况的操作次数后，就可以进行统计了，看所有数转换为哪个 F 操作数最少
        int numOps=0;
        int res=2*n;
        for(int F=2;F<=(limit<<1);F++){
            numOps+=diff[F];
            res=min(res,numOps);
        }
        return res;
    }
};

2 个帖子 - 2 位参与者

阅读完整话题