Question

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

English Version

题目描述

给你两个正整数数组 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 相似。

解法

方法一：奇偶分类 + 排序

注意到，由于每次操作，元素的值只会增加 $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$ 的长度。

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

class Solution {
  public long makeSimilar(int[] nums, int[] target) {
    Arrays.sort(nums);
    Arrays.sort(target);
    List<Integer> a1 = new ArrayList<>();
    List<Integer> a2 = new ArrayList<>();
    List<Integer> b1 = new ArrayList<>();
    List<Integer> b2 = new ArrayList<>();
    for (int v : nums) {
      if (v % 2 == 0) {
        a1.add(v);
      } else {
        a2.add(v);
      }
    }
    for (int v : target) {
      if (v % 2 == 0) {
        b1.add(v);
      } else {
        b2.add(v);
      }
    }
    long ans = 0;
    for (int i = 0; i < a1.size(); ++i) {
      ans += Math.abs(a1.get(i) - b1.get(i));
    }
    for (int i = 0; i < a2.size(); ++i) {
      ans += Math.abs(a2.get(i) - b2.get(i));
    }
    return ans / 4;
  }
}

class Solution {
public:
  long long makeSimilar(vector<int>& nums, vector<int>& target) {
    sort(nums.begin(), nums.end());
    sort(target.begin(), target.end());
    vector<int> a1;
    vector<int> a2;
    vector<int> b1;
    vector<int> b2;
    for (int v : nums) {
      if (v & 1)
        a1.emplace_back(v);
      else
        a2.emplace_back(v);
    }
    for (int v : target) {
      if (v & 1)
        b1.emplace_back(v);
      else
        b2.emplace_back(v);
    }
    long long ans = 0;
    for (int i = 0; i < a1.size(); ++i) ans += abs(a1[i] - b1[i]);
    for (int i = 0; i < a2.size(); ++i) ans += abs(a2[i] - b2[i]);
    return ans / 4;
  }
};

func makeSimilar(nums []int, target []int) int64 {
  sort.Ints(nums)
  sort.Ints(target)
  a1, a2, b1, b2 := []int{}, []int{}, []int{}, []int{}
  for _, v := range nums {
    if v%2 == 0 {
      a1 = append(a1, v)
    } else {
      a2 = append(a2, v)
    }
  }
  for _, v := range target {
    if v%2 == 0 {
      b1 = append(b1, v)
    } else {
      b2 = append(b2, v)
    }
  }
  ans := 0
  for i := 0; i < len(a1); i++ {
    ans += abs(a1[i] - b1[i])
  }
  for i := 0; i < len(a2); i++ {
    ans += abs(a2[i] - b2[i])
  }
  return int64(ans / 4)
}

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

function makeSimilar(nums: number[], target: number[]): number {
  nums.sort((a, b) => a - b);
  target.sort((a, b) => a - b);

  const a1: number[] = [];
  const a2: number[] = [];
  const b1: number[] = [];
  const b2: number[] = [];

  for (const v of nums) {
    if (v % 2 === 0) {
      a1.push(v);
    } else {
      a2.push(v);
    }
  }

  for (const v of target) {
    if (v % 2 === 0) {
      b1.push(v);
    } else {
      b2.push(v);
    }
  }

  let ans = 0;
  for (let i = 0; i < a1.length; ++i) {
    ans += Math.abs(a1[i] - b1[i]);
  }

  for (let i = 0; i < a2.length; ++i) {
    ans += Math.abs(a2[i] - b2[i]);
  }

  return ans / 4;
}