Medium

题目描述

给定一个大小为 n 的整数数组 nums，其中 n 是偶数，以及一个整数 k。

你可以对数组进行一些修改，在一次修改中，你可以将数组中的任意元素替换为范围 [0, k] 内的任意整数。

你需要进行一些修改（可能不修改），使得最终数组满足以下条件：

  • 存在一个整数 X，使得对于所有 0 <= i < n，都有 abs(a[i] - a[n - i - 1]) = X。

返回满足上述条件所需的最少修改次数。

示例 1：

输入：nums = [1,0,1,2,4,3], k = 4
输出：2
解释：
我们可以进行以下修改：
- 将 nums[1] 替换为 2。结果数组为 nums = [1,2,1,2,4,3]。
- 将 nums[3] 替换为 3。结果数组为 nums = [1,2,1,3,4,3]。
整数 X 为 2。

示例 2：

输入：nums = [0,1,2,3,3,6,5,4], k = 6
输出：2
解释：
我们可以进行以下操作：
- 将 nums[3] 替换为 0。结果数组为 nums = [0,1,2,0,3,6,5,4]。
- 将 nums[4] 替换为 4。结果数组为 nums = [0,1,2,0,4,6,5,4]。
整数 X 为 4。

约束条件：

  • 2 <= n == nums.length <= 10^5
  • n 是偶数
  • 0 <= nums[i] <= k <= 10^5

解题思路

这个问题的核心是要找到一个目标差值 X，使得通过最少的修改次数让所有对称位置的元素差值都等于 X。

解题思路：

  1. 配对分析：将数组按对称位置配对，即 (nums[i], nums[n-1-i])，共有 n/2 对。

  2. 枚举目标差值：X 的可能取值范围是 [0, k]。对于每个可能的 X，计算需要的修改次数。

  3. 计算修改次数：对于每一对 (a, b) 和目标差值 X：

    • 如果 |a - b| = X，不需要修改（0次）
    • 如果可以通过修改其中一个元素达到差值 X，需要1次修改
    • 否则需要修改两个元素，需要2次修改

  4. 优化计算：使用差分数组技巧来高效计算所有可能 X 值对应的修改次数。

关键观察：

  • 对于一对 (a, b)，如果要达到差值 X 且只修改一个元素，那么修改后的值必须在 [0, k] 范围内
  • 可以通过分析每对元素对不同 X 值的贡献，使用差分数组批量更新

算法步骤：

  1. 计算每对元素的当前差值
  2. 对于每对，分析在什么 X 值范围内需要 0/1/2 次修改
  3. 使用差分数组技巧统计每个 X 值对应的总修改次数
  4. 返回最小修改次数

代码实现

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> diff(k + 2, 0); // 差分数组
        int totalPairs = n / 2;
        
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];
            int currentDiff = abs(a - b);
            
            // 当前差值不需要修改
            diff[currentDiff]--;
            diff[currentDiff + 1]++;
            
            // 计算只需要修改一个元素就能达到的差值范围
            int maxPossible = max({a, b, k - a, k - b});
            
            // 差值在 [0, maxPossible] 范围内只需要修改一个元素
            // 超出这个范围需要修改两个元素
            diff[maxPossible + 1]++;
        }
        
        // 应用差分数组，计算每个X值对应的修改次数
        int changes = totalPairs * 2; // 初始假设所有对都需要修改2次
        int result = changes;
        
        for (int x = 0; x <= k; x++) {
            changes += diff[x];
            result = min(result, changes);
        }
        
        return result;
    }
};

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        n = len(nums)
        diff = [0] * (k + 2)  # 差分数组
        total_pairs = n // 2
        
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            current_diff = abs(a - b)
            
            # 当前差值不需要修改
            diff[current_diff] -= 1
            if current_diff + 1 <= k:
                diff[current_diff + 1] += 1
            
            # 计算只需要修改一个元素就能达到的最大差值
            max_possible = max(a, b, k - a, k - b)
            
            # 超出最大可能差值需要修改两个元素
            if max_possible + 1 <= k:
                diff[max_possible + 1] += 1
        
        # 应用差分数组，计算每个X值对应的修改次数
        changes = total_pairs * 2  # 初始假设所有对都需要修改2次
        result = changes
        
        for x in range(k + 1):
            changes += diff[x]
            result = min(result, changes)
        
        return result

public class Solution {
    public int MinChanges(int[] nums, int k) {
        int n = nums.Length;
        int[] diff = new int[k + 2]; // 差分数组
        int totalPairs = n / 2;
        
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];
            int currentDiff = Math.Abs(a - b);
            
            // 当前差值不需要修改
            diff[currentDiff]--;
            if (currentDiff + 1 <= k) {
                diff[currentDiff + 1]++;
            }
            
            // 计算只需要修改一个元素就能达到的最大差值
            int maxPossible = Math.Max(Math.Max(a, b), Math.Max(k - a, k - b));
            
            // 超出最大可能差值需要修改两个元素
            if (maxPossible + 1 <= k) {
                diff[maxPossible + 1]++;
            }
        }
        
        // 应用差分数组，计算每个X值对应的修改次数
        int changes = totalPairs * 2; // 初始假设所有对都需要修改2次
        int result = changes;
        
        for (int x = 0; x <= k; x++) {
            changes += diff[x];
            result = Math.Min(result, changes);
        }
        
        return result;
    }
}

var minChanges = function(nums, k) {
    const n = nums.length;
    const diff = new Array(k + 2).fill(0); // 差分数组
    const totalPairs = Math.floor(n / 2);
    
    for (let i = 0; i < Math.floor(n / 2); i++) {
        const a = nums[i];
        const b = nums[n - 1 - i];
        const currentDiff = Math.abs(a - b);
        
        // 当前差值不需要修改
        diff[currentDiff]--;
        if (currentDiff + 1 <= k) {
            diff[currentDiff + 1]++;
        }
        
        // 计算只需要修改一个元素就能达到的最大差值
        const maxPossible = Math.max(a, b, k - a, k - b);
        
        // 超出最大可能差值需要修改两个元素
        if (maxPossible + 1 <= k) {
            diff[maxPossible + 1]++;
        }
    }
    
    // 应用差分数组，计算每个X值对应的修改次数
    let changes = totalPairs * 2; // 初始假设所有对都需要修改2次
    let result = changes;
    
    for (let x = 0; x <= k; x++) {
        changes += diff[x];
        result = Math.min(result, changes);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + k)遍历数组一次 O(n)，应用差分数组 O(k)
空间复杂度O(k)差分数组的空间开销