What is the key strategy for Minimum Number of Operations to Make Arrays Similar?

The main strategy is to separate even and odd numbers, sort them, compute differences, and use greedy pair adjustments to minimize operations.

Do I need to match sums of nums and target before operations?

Matching sums is necessary but not sufficient; you must also align frequencies and parity to ensure valid operations.

Can I perform multiple operations on the same index?

Yes, indices can be used repeatedly as long as each operation follows the ±2 adjustment rule and parity is preserved.

What is the complexity of this approach?

Time complexity is O(n log n) for sorting and O(n) for difference computations and greedy operations. Space complexity is O(n) for temporary arrays.

Why split arrays by parity in this problem pattern?

Splitting by parity ensures all operations are valid, prevents impossible transformations, and aligns with the greedy invariant approach of this problem.

#2449

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你两个正整数数组 nums 和 target ，两个数组长度相等。在一次操作中，你可以选择两个不同的下标 i 和 j ，其中 0 ，并且：令 nums[i] = nums[i] + 2 且令 nums[j] = nums[j] - 2 。如果两个数组中每个元素出现的频率相等，我们称两个…

数组贪心排序

题目描述

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

lightbulb

解题思路

方法一：奇偶分类 + 排序

注意到，由于每次操作，元素的值只会增加 $2$ 或减少 $2$ ，因此，元素的奇偶性不会改变。

因此，我们可以将数组 $nums$ 和 $target$ 分别按奇偶性分为两组，分别记为 $a_1$ 和 $a_2$ ，以及 $b_1$ 和 $b_2$ 。

那么，我们只需要将 $a_1$ 中的元素与 $b_1$ 中的元素配对，将 $a_2$ 中的元素与 $b_2$ 中的元素配对，然后进行操作。配对的过程中，我们可以使用贪心的策略，每次将 $a_i$ 中较小的元素与 $b_i$ 中较小的元素配对，这样可以保证操作的次数最少。这里可以直接通过排序来实现。

由于每次操作，都可以将对应位置的元素差值减少 $4$ ，因此，我们累计每个对应位置的差值，最后除以 $4$ 即可得到答案。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
        nums.sort(key=lambda x: (x & 1, x))
        target.sort(key=lambda x: (x & 1, x))
        return sum(abs(a - b) for a, b in zip(nums, target)) // 4

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you consider parity separately to avoid invalid operations.
question_mark
Observes whether you identify that sum invariants guarantee feasibility of transformations.
question_mark
Watches if you optimize operations using sorted differences rather than brute force.

warning

常见陷阱

外企场景

error
Failing to separate even and odd numbers, causing impossible operations.
error
Miscounting operations by not pairing differences optimally, leading to non-minimal results.
error
Assuming identical sums of arrays is sufficient without verifying frequency alignment.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing operations of ±k instead of ±2, requiring adjustment to the greedy pairing calculation.
arrow_right_alt
Arrays with negative numbers, introducing additional parity and difference handling complexity.
arrow_right_alt
Determining the minimum operations under a restricted set of indices instead of any two elements.

help

常见问题

外企场景

继续练习

#2448 使数组相等的最小开销 #2412 完成所有交易的初始最少钱数 #2410 运动员和训练师的最大匹配数