给你一个长度为 偶数 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 。
返回使数组 互补 的 最少 操作次数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-moves-to-make-array-complementary
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public static int minMoves(int[] nums, int limit) {
if (nums == null || nums.length == 0) {
return 0;
}
// [2, 2 * limit]
// [2, min]: 2
// [min + 1, min + max - 1]: 1
// min + max: 0
// [min + max + 1, max + limit]: 1
// [max + limit + 1, 2 * limit]: 2
int[] d = new int[limit << 1 | 1];
// 0 1 2 3
for (int i = 0; i < nums.length / 2; ++i) {
int min = Math.min(nums[i], nums[nums.length - i - 1]);
int max = Math.max(nums[i], nums[nums.length - i - 1]);
d[2] += 2;
if (1 + min >= 2 && 1 + min <= 2 * limit) {
d[1 + min] -= 1;
}
if (max + limit + 1 >= 2 && max + limit + 1 <= 2 * limit) {
d[max + limit + 1] += 1;
}
if (min + max >= 2 && min + max <= 2 * limit) {
d[min + max] -= 1;
}
if (min + max + 1 >= 2 && min + max + 1 <= 2 * limit) {
d[min + max + 1] += 1;
}
}
int sum = 0, ret = nums.length;
for (int i = 2; i <= 2 * limit; ++i) {
sum += d[i];
ret = Math.min(ret, sum);
}
return ret;
}
}