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

给你一个长度为 偶数 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;
    }
}
上一篇:惠农10号,黄骨鱼肉质鲜嫩且营养丰富


下一篇:数据库分库分表后”跨库分页“查询方案