Hard

题目描述

给你两个正整数数组 nums 和 target，两个数组长度相等。

在一次操作中，你可以选择两个不同的下标 i 和 j，其中 0 <= i, j < nums.length，并且：

  • 将 nums[i] 设为 nums[i] + 2
  • 将 nums[j] 设为 nums[j] - 2

如果两个数组中每个元素的频次都相同，则认为两个数组是相似的。

返回使 nums 和 target 相似所需的最少操作数。测试用例保证 nums 一定可以变得与 target 相似。

示例 1：

输入：nums = [8,12,6], target = [2,14,10]
输出：2
解释：可以用两次操作使 nums 和 target 相似：
- 选择 i = 0 和 j = 2，nums = [10,12,4]
- 选择 i = 1 和 j = 2，nums = [10,14,2]
可以证明需要的最少操作数是 2。

示例 2：

输入：nums = [1,2,5], target = [4,1,3]
输出：1
解释：我们可以用一次操作使 nums 和 target 相似：
- 选择 i = 1 和 j = 2，nums = [1,4,3]

示例 3：

输入：nums = [1,1,1,1,1], target = [1,1,1,1,1]
输出：0
解释：数组 nums 已经与 target 相似。

提示：

  • n == nums.length == target.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], target[i] <= 10^6
  • 题目保证可以使 nums 变得与 target 相似

解题思路

解题思路

观察操作规律：每次操作只能对两个数分别 +2 和 -2，这意味着数组的奇偶性不会改变。也就是说，奇数只能变成奇数，偶数只能变成偶数。

基于这个关键观察，我们可以将问题分解：

  1. 分离奇偶数：将 nums 和 target 分别按奇偶性分组
  2. 贪心匹配：对于奇数组和偶数组，分别进行排序后贪心匹配
  3. 计算操作数：每一对匹配需要的操作数是差值的绝对值除以 2

为什么贪心策略是正确的？

  • 排序后，最小的元素匹配最小的目标，可以确保总的移动距离最小
  • 由于每次操作涉及两个数的相反变化，我们实际上是在重新分配数值
  • 贪心匹配能够最小化总的重新分配成本

算法步骤：

  1. 分别提取 nums 和 target 的奇数和偶数
  2. 对奇数组和偶数组分别排序
  3. 逐一配对，计算需要从一个数"转移"到另一个数的量
  4. 由于每次操作转移 2 个单位，所以操作数是转移量的一半
  5. 只计算需要增加的部分（减少的部分会被增加的部分平衡）

时间复杂度主要由排序决定，空间复杂度用于存储分离后的数组。

代码实现

class Solution {
public:
    long long makeSimilar(vector<int>& nums, vector<int>& target) {
        vector<int> numsOdd, numsEven, targetOdd, targetEven;
        
        // 分离奇偶数
        for (int num : nums) {
            if (num % 2 == 0) numsEven.push_back(num);
            else numsOdd.push_back(num);
        }
        
        for (int num : target) {
            if (num % 2 == 0) targetEven.push_back(num);
            else targetOdd.push_back(num);
        }
        
        // 排序
        sort(numsOdd.begin(), numsOdd.end());
        sort(numsEven.begin(), numsEven.end());
        sort(targetOdd.begin(), targetOdd.end());
        sort(targetEven.begin(), targetEven.end());
        
        long long operations = 0;
        
        // 计算奇数需要的操作
        for (int i = 0; i < numsOdd.size(); i++) {
            if (targetOdd[i] > numsOdd[i]) {
                operations += (targetOdd[i] - numsOdd[i]) / 2;
            }
        }
        
        // 计算偶数需要的操作
        for (int i = 0; i < numsEven.size(); i++) {
            if (targetEven[i] > numsEven[i]) {
                operations += (targetEven[i] - numsEven[i]) / 2;
            }
        }
        
        return operations;
    }
};

class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
        # 分离奇偶数
        nums_odd = [x for x in nums if x % 2 == 1]
        nums_even = [x for x in nums if x % 2 == 0]
        target_odd = [x for x in target if x % 2 == 1]
        target_even = [x for x in target if x % 2 == 0]
        
        # 排序
        nums_odd.sort()
        nums_even.sort()
        target_odd.sort()
        target_even.sort()
        
        operations = 0
        
        # 计算奇数需要的操作
        for i in range(len(nums_odd)):
            if target_odd[i] > nums_odd[i]:
                operations += (target_odd[i] - nums_odd[i]) // 2
        
        # 计算偶数需要的操作
        for i in range(len(nums_even)):
            if target_even[i] > nums_even[i]:
                operations += (target_even[i] - nums_even[i]) // 2
        
        return operations

public class Solution {
    public long MakeSimilar(int[] nums, int[] target) {
        var numsOdd = new List<int>();
        var numsEven = new List<int>();
        var targetOdd = new List<int>();
        var targetEven = new List<int>();
        
        // 分离奇偶数
        foreach (int num in nums) {
            if (num % 2 == 0) numsEven.Add(num);
            else numsOdd.Add(num);
        }
        
        foreach (int num in target) {
            if (num % 2 == 0) targetEven.Add(num);
            else targetOdd.Add(num);
        }
        
        // 排序
        numsOdd.Sort();
        numsEven.Sort();
        targetOdd.Sort();
        targetEven.Sort();
        
        long operations = 0;
        
        // 计算奇数需要的操作
        for (int i = 0; i < numsOdd.Count; i++) {
            if (targetOdd[i] > numsOdd[i]) {
                operations += (targetOdd[i] - numsOdd[i]) / 2;
            }
        }
        
        // 计算偶数需要的操作
        for (int i = 0; i < numsEven.Count; i++) {
            if (targetEven[i] > numsEven[i]) {
                operations += (targetEven[i] - numsEven[i]) / 2;
            }
        }
        
        return operations;
    }
}

var makeSimilar = function(nums, target) {
    const evenNums = nums.filter(x => x % 2 === 0).sort((a, b) => a - b);
    const oddNums = nums.filter(x => x % 2 === 1).sort((a, b) => a - b);
    const evenTarget = target.filter(x => x % 2 === 0).sort((a, b) => a - b);
    const oddTarget = target.filter(x => x % 2 === 1).sort((a, b) => a - b);
    
    let operations = 0;
    
    for (let i = 0; i < evenNums.length; i++) {
        if (evenNums[i] > evenTarget[i]) {
            operations += (evenNums[i] - evenTarget[i]) / 2;
        }
    }
    
    for (let i = 0; i < oddNums.length; i++) {
        if (oddNums[i] > oddTarget[i]) {
            operations += (oddNums[i] - oddTarget[i]) / 2;
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：O(n log n)，主要由排序操作决定
  • 空间复杂度：O(n)，用于存储分离后的奇偶数数组

相关题目