class Solution {
public:
int minMoves(vector<int>& nums, int limit) {
}
};
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.length2 <= n <= 1051 <= nums[i] <= limit <= 105n 是偶数。原站题解
cpp 解法, 执行用时: 108 ms, 内存消耗: 86.8 MB, 提交时间: 2023-08-12 00:03:50
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;
}
};
cpp 解法, 执行用时: 116 ms, 内存消耗: 86.8 MB, 提交时间: 2023-08-12 00:02:38
/**
* 差分+扫描
* (a, b) 数对, 和target
* 我们可以遍历数组中的所有数对，求出每个数对的这四个关键位置，然后更新差分数组。
* 最后，我们遍历（扫描）差分数组，就可以找到令总操作次数最小的target，同时可以得到最少的操作次数。
*/
class Solution {
public:
int minMoves(vector<int>& nums, int limit) {
int n = nums.size();
vector<int> delta(limit * 2 + 2);
for (int i = 0; i < n / 2; ++i) {
int lo = 1 + min(nums[i], nums[n - i - 1]);
int hi = limit + max(nums[i], nums[n - i - 1]);
int sum = nums[i] + nums[n - i - 1];
delta[lo]--;
delta[sum]--;
delta[sum + 1]++;
delta[hi + 1]++;
}
int now = n;
int ans = n;
for (int i = 2; i <= limit * 2; ++i) {
now += delta[i];
ans = min(ans, now);
}
return ans;
}
};