2449-使数组相似的最少操作次数

给你两个正整数数组 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 <= 105
• 1 <= nums[i], target[i] <= 106
• nums 一定可以变得与 target 相似。

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

提示 1

如果把问题中的 +2 和 -2 改成 +1 和 -1，要怎么做？

例如 nums}=[2,8]，target}=[4,6]，那么应该让 2 和 4 一对，8 和 6 一对。如果让 2 和 6 一对，8 和 4 一对，是会让变化量的和变得更大的。

通过这种邻项交换法，我们可以证明，让最小的一对，次小的一对，第三小的一对，……，累加每对元素的差的绝对值，就得到了每个数的变化量的和的最小值。

提示 2

回到原问题，+2 和 -2 会导致无法直接排序然后一一匹配，但注意到 +2 和 -2 并不会改变元素的奇偶性，因此我们可以把偶数分为一组，奇数分为一组，每组分别计算，这样就像提示 1 那样一一匹配了。

最后把变化量的和除以 4，即为答案。

提示 3

代码实现时可以先奇数再偶数，然后奇数偶数内部再排序。

由于数组元素都是正数，可以先把所有奇数变成相反数，然后排序，奇偶就自动分开了。

[sol1-Python3]

def f(a: List[int]) -> None:
    for i, x in enumerate(a):
        if x % 2: a[i] = -x  # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
    a.sort()

class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
        f(nums)
        f(target)
        return sum(abs(x - y) for x, y in zip(nums, target)) // 4

[sol1-Java]

class Solution {
    public long makeSimilar(int[] nums, int[] target) {
        f(nums);
        f(target);
        var ans = 0L;
        for (var i = 0; i < nums.length; ++i)
            ans += Math.abs(nums[i] - target[i]);
        return ans / 4;
    }

    private void f(int[] a) {
        // 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
        for (var i = 0; i < a.length; ++i)
            if (a[i] % 2 != 0) a[i] = -a[i];
        Arrays.sort(a);
    }
}

[sol1-C++]

class Solution {
    void f(vector<int> &a) {
        for (int &x : a)
            if (x % 2) x = -x; // 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
        sort(a.begin(), a.end());
    }

public:
    long long makeSimilar(vector<int> &nums, vector<int> &target) {
        f(nums);
        f(target);
        long long ans = 0L;
        for (int i = 0; i < nums.size(); ++i)
            ans += abs(nums[i] - target[i]);
        return ans / 4;
    }
};

[sol1-Go]

func f(a []int) {
	for i, x := range a {
		if x%2 > 0 {
			a[i] = -x // 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
		}
	}
	sort.Ints(a)
}

func makeSimilar(nums, target []int) (ans int64) {
	f(nums)
	f(target)
	for i, x := range nums {
		ans += int64(abs(x - target[i]))
	}
	return ans / 4
}

func abs(x int) int { if x < 0 { return -x }; return x }

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。
• 空间复杂度：O(1)。忽略快排的栈开销。