Question

2499. 让数组不相等的最小总代价

English Version

题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。

每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。

你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的 最小 总代价。

请你返回让_ _nums1 和 nums2_ _满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。

 

示例 1：

输入：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
输出：10
解释：
实现目标的其中一种方法为：
- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法，但是无法得到代价和小于 10 的方案。

示例 2：

输入：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
输出：10
解释：
实现目标的一种方法为：
- 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。
- 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。
总代价为 10 ，是所有方案中的最小代价。

示例 3：

输入：nums1 = [1,2,2], nums2 = [1,2,2]
输出：-1
解释：
不管怎么操作，都无法满足题目要求。
所以返回 -1 。

 

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= n

解法

方法一：贪心

我们先同时遍历数组 nums1 和 nums2，统计相同位置上的值相同的个数 same，这些位置上的值必须交换，因此，将这些位置下标累加到答案中。另外，用数组或哈希表 cnt 统计这些相同值的出现次数。

如果所有相同值的出现次数均不超过 same 的一半，那么意味着，我们可以在其内部，通过两两交换，使得对应位置上的值不同，而这些交换，已经在上面累加下标时计入了答案中了，无需额外的代价。否则，如果某个值的出现次数超过 same 的一半，那么对于这个值就是多出的个数，我们需要在数组的其他位置上找到合适的，进行交换。这里我们可以直接遍历一遍数组得出。

如果最终还有剩余位置未能交换，说明无法达成目标，返回 $-1$ 即可，否则返回答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 nums1 或 nums2 的长度。

class Solution:
  def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
    ans = same = 0
    cnt = Counter()
    for i, (a, b) in enumerate(zip(nums1, nums2)):
      if a == b:
        same += 1
        ans += i
        cnt[a] += 1

    m = lead = 0
    for k, v in cnt.items():
      if v * 2 > same:
        m = v * 2 - same
        lead = k
        break
    for i, (a, b) in enumerate(zip(nums1, nums2)):
      if m and a != b and a != lead and b != lead:
        ans += i
        m -= 1
    return -1 if m else ans

class Solution {
  public long minimumTotalCost(int[] nums1, int[] nums2) {
    long ans = 0;
    int same = 0;
    int n = nums1.length;
    int[] cnt = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      if (nums1[i] == nums2[i]) {
        ans += i;
        ++same;
        ++cnt[nums1[i]];
      }
    }
    int m = 0, lead = 0;
    for (int i = 0; i < cnt.length; ++i) {
      int t = cnt[i] * 2 - same;
      if (t > 0) {
        m = t;
        lead = i;
        break;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (m > 0 && nums1[i] != nums2[i] && nums1[i] != lead && nums2[i] != lead) {
        ans += i;
        --m;
      }
    }
    return m > 0 ? -1 : ans;
  }
}

class Solution {
public:
  long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
    long long ans = 0;
    int same = 0;
    int n = nums1.size();
    int cnt[n + 1];
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i) {
      if (nums1[i] == nums2[i]) {
        ans += i;
        ++same;
        ++cnt[nums1[i]];
      }
    }
    int m = 0, lead = 0;
    for (int i = 0; i < n + 1; ++i) {
      int t = cnt[i] * 2 - same;
      if (t > 0) {
        m = t;
        lead = i;
        break;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (m > 0 && nums1[i] != nums2[i] && nums1[i] != lead && nums2[i] != lead) {
        ans += i;
        --m;
      }
    }
    return m > 0 ? -1 : ans;
  }
};

func minimumTotalCost(nums1 []int, nums2 []int) (ans int64) {
  same, n := 0, len(nums1)
  cnt := make([]int, n+1)
  for i, a := range nums1 {
    b := nums2[i]
    if a == b {
      same++
      ans += int64(i)
      cnt[a]++
    }
  }
  var m, lead int
  for i, v := range cnt {
    if t := v*2 - same; t > 0 {
      m = t
      lead = i
      break
    }
  }
  for i, a := range nums1 {
    b := nums2[i]
    if m > 0 && a != b && a != lead && b != lead {
      ans += int64(i)
      m--
    }
  }
  if m > 0 {
    return -1
  }
  return ans
}