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

标签: 贪心 数组 排序

难度: 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 <= 105
  • 1 <= nums[i], target[i] <= 106
  • nums 一定可以变得与 target 相似。

Submission

运行时间: 148 ms

内存: 31.9 MB

# -*- coding: utf-8 -*-
from typing import List, Tuple, Optional
from collections import deque, Counter
from queue import PriorityQueue
import math
from functools import lru_cache
# from sortedcontainers import SortedDict, SortedSet
import random
import copy
import sys
import bisect

sys.setrecursionlimit(9999999)
MOD = 10**9 + 7

class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:

        def solve(v1, v2):
            v1.sort()
            v2.sort()

            tot = 0
            for x, y in zip(v1, v2):
                if x > y:
                   tot += (x-y) >> 1
            return tot

        ans = 0
        v1 = [v for v in nums if v&1]
        v2 = [v for v in target if v&1]
        ans += solve(v1, v2)

        v1 = [v for v in nums if not (v&1)]
        v2 = [v for v in target if not (v&1)]
        ans += solve(v1, v2)

        return ans

Explain

该题解的思路基于将两个数组分别变为相似的过程。首先，将nums和target数组分别按奇偶性分开，形成四个子数组：nums的奇数部分、nums的偶数部分、target的奇数部分和target的偶数部分。针对这四个子数组，我们只需要分别使nums的奇数部分与target的奇数部分相似，以及nums的偶数部分与target的偶数部分相似即可。为了实现这一点，对于每个子数组，我们首先对其进行排序，然后逐对比较元素。如果nums中的元素大于target中的对应元素，我们计算差值的一半(因为每次操作改变的总和为2)并累加至操作次数。最后将奇数部分和偶数部分所需的操作次数求和，得到总的最少操作次数。

时间复杂度: O(n log n)

空间复杂度: O(n)

# -*- coding: utf-8 -*-
from typing import List

class Solution:
    def makeSimilar(self, nums: List[int], target: List[int]) -> int:
        # 解决v1到v2的相似转换问题
        def solve(v1, v2):
            v1.sort()  # 对v1排序
            v2.sort()  # 对v2排序

            tot = 0  # 初始化操作计数
            for x, y in zip(v1, v2):  # 遍历排序后的数组元素
                if x > y:  # 如果当前nums元素大于target元素
                   tot += (x-y) >> 1  # 计算差值的一半并累加至tot
            return tot  # 返回该部分的总操作数

        ans = 0  # 初始化总操作数
        v1 = [v for v in nums if v&1]  # 提取nums中的奇数部分
        v2 = [v for v in target if v&1]  # 提取target中的奇数部分
        ans += solve(v1, v2)  # 计算奇数部分的操作数并累加

        v1 = [v for v in nums if not (v&1)]  # 提取nums中的偶数部分
        v2 = [v for v in target if not (v&1)]  # 提取target中的偶数部分
        ans += solve(v1, v2)  # 计算偶数部分的操作数并累加

        return ans  # 返回总操作数

Explore

在这个问题中，每次操作可以使一个元素增加2，另一个元素减少2。这样的操作保持了每个元素奇偶性的不变性，即奇数加2或减2后仍为奇数，偶数同理。因此，为了确保最终的`nums`数组与`target`数组在元素频率上相等，我们必须单独考虑奇数和偶数，确保奇数部分的元素可以通过有限操作转换为目标奇数部分，偶数部分同理。这种分法可以减少问题的复杂性，允许我们独立处理两部分，简化操作过程和计算。

题解中只计算了`nums`元素大于`target`元素的情况，这是因为如果`nums`中的元素小于`target`中的元素，通过排序和索引匹配，这种情况会自动平衡。具体来说，如果一个较小的`nums`元素与较大的`target`元素对应，那么在其他位置一定存在一个较大的`nums`元素与较小的`target`元素对应，以保持两个数组的总和相同。因此，对于每一对`x > y`的情况，我们计算差值并除以2来确定操作数，而对于`x < y`的情况，它将被`x > y`的对应情况所平衡。

使用`(x-y) >> 1`来计算操作次数是因为每次操作改变的总量为2（一个元素加2，另一个减2），因此当我们发现`nums`中的元素`x`比`target`中的元素`y`大时，差值`x-y`表示为了匹配这两个元素，我们需要减小`x`或增加`y`的总量。由于每次操作改变的总量为2，所以将差值除以2（在计算中使用位移操作`>> 1`实现除以2）得到实际的操作次数。这样的计算考虑到了每对不匹配元素之间的差值，并且是准确的，前提是保持两个数组的元素总和相等，这在题设中是由排序和逐一比较保证的。