Medium

题目描述

给定两个整数数组 nums1（长度为 n）和 nums2（长度为 n + 1）。

你希望使用最少的操作次数将 nums1 转换为 nums2。

你可以执行以下操作任意次数，每次选择一个索引 i：

  • 将 nums1[i] 增加 1
  • 将 nums1[i] 减少 1
  • 将 nums1[i] 追加到数组末尾

返回将 nums1 转换为 nums2 所需的最少操作次数。

示例 1：

输入：nums1 = [2,8], nums2 = [1,7,3]
输出：4

示例 2：

输入：nums1 = [1,3,6], nums2 = [2,4,5,3]
输出：4

示例 3：

输入：nums1 = [2], nums2 = [3,4]
输出：3

提示：

  • 1 <= n == nums1.length <= 10^5
  • nums2.length == n + 1
  • 1 <= nums1[i], nums2[i] <= 10^5

解题思路

这道题的核心在于理解 nums2 比 nums1 多一个元素，这个额外元素必须通过追加操作产生。

解题思路：

  1. 关键观察：由于 nums2 长度比 nums1 多1，我们需要选择 nums1 中的某个位置 j 进行追加操作。追加后，nums1[j] 需要同时匹配 nums2[j] 和 nums2 的最后一个元素。

  2. 策略枚举：对于每个可能的追加位置 j（0 到 n），计算总操作成本：

    • 将 nums1[j] 调整为 nums2[j] 的成本
    • 将追加的 nums1[j] 调整为 nums2[n] 的成本
    • 其他位置 i（i ≠ j）调整为 nums2[i] 的成本

  3. 优化计算：使用前缀和技术避免重复计算。预计算所有位置调整到目标值的总成本，然后减去选中位置的成本，加上该位置的特殊成本。

  4. 边界处理：当 j = n 时，表示在末尾追加一个新元素，此时 nums1 的所有原始元素都需要正常调整。

时间复杂度：O(n)，每个位置只计算一次 空间复杂度：O(1)，只使用常数额外空间

代码实现

class Solution {
public:
    long long minOperations(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        
        // 计算基础成本：所有位置都正常调整的总成本
        long long baseCost = 0;
        for (int i = 0; i < n; i++) {
            baseCost += abs(nums1[i] - nums2[i]);
        }
        
        long long minCost = LLONG_MAX;
        
        // 尝试在每个位置 j 进行追加操作
        for (int j = 0; j <= n; j++) {
            long long cost;
            
            if (j == n) {
                // 在末尾追加新元素
                cost = baseCost + abs(nums1[0] - nums2[n]);
            } else {
                // 在位置 j 追加元素
                cost = baseCost 
                     - abs(nums1[j] - nums2[j])  // 减去位置j的原始成本
                     + abs(nums1[j] - nums2[j])  // 调整nums1[j]到nums2[j]
                     + abs(nums1[j] - nums2[n]); // 调整追加元素到nums2[n]
            }
            
            minCost = min(minCost, cost);
        }
        
        return minCost;
    }
};

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        
        # 计算基础成本：所有位置都正常调整的总成本
        base_cost = sum(abs(nums1[i] - nums2[i]) for i in range(n))
        
        min_cost = float('inf')
        
        # 尝试在每个位置 j 进行追加操作
        for j in range(n + 1):
            if j == n:
                # 在末尾追加新元素
                cost = base_cost + abs(nums1[0] - nums2[n])
            else:
                # 在位置 j 追加元素
                cost = (base_cost 
                       - abs(nums1[j] - nums2[j])  # 减去位置j的原始成本
                       + abs(nums1[j] - nums2[j])  # 调整nums1[j]到nums2[j]
                       + abs(nums1[j] - nums2[n]))  # 调整追加元素到nums2[n]
            
            min_cost = min(min_cost, cost)
        
        return min_cost

public class Solution {
    public long MinOperations(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        
        // 计算基础成本：所有位置都正常调整的总成本
        long baseCost = 0;
        for (int i = 0; i < n; i++) {
            baseCost += Math.Abs(nums1[i] - nums2[i]);
        }
        
        long minCost = long.MaxValue;
        
        // 尝试在每个位置 j 进行追加操作
        for (int j = 0; j <= n; j++) {
            long cost;
            
            if (j == n) {
                // 在末尾追加新元素
                cost = baseCost + Math.Abs(nums1[0] - nums2[n]);
            } else {
                // 在位置 j 追加元素
                cost = baseCost 
                     - Math.Abs(nums1[j] - nums2[j])  // 减去位置j的原始成本
                     + Math.Abs(nums1[j] - nums2[j])  // 调整nums1[j]到nums2[j]
                     + Math.Abs(nums1[j] - nums2[n]); // 调整追加元素到nums2[n]
            }
            
            minCost = Math.Min(minCost, cost);
        }
        
        return minCost;
    }
}

var minOperations = function(nums1, nums2) {
    const n = nums1.length;
    const memo = new Map();
    
    function solve(i, mask) {
        if (i === n + 1) return 0;
        
        const key = `${i},${mask}`;
        if (memo.has(key)) return memo.get(key);
        
        let result = Infinity;
        
        // Try to match nums2[i] with each available element from nums1
        for (let j = 0; j < n; j++) {
            if (mask & (1 << j)) continue; // Element j already used
            
            const cost = Math.abs(nums1[j] - nums2[i]);
            result = Math.min(result, cost + solve(i + 1, mask | (1 << j)));
        }
        
        memo.set(key, result);
        return result;
    }
    
    return solve(0, 0) + 1; // +1 for the append operation
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要遍历所有可能的追加位置，每个位置的计算都是O(1)
空间复杂度O(1) - 只使用常数额外空间存储成本计算结果