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

题目描述

leetcode 困难题

给你两个下标从 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 的方案。

提示1：

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

分类讨论 + 贪心

定义所有 $num1[i] == num2[i]$ 的总次数为 $count$，众数为 $most$，众数相等的次数为 $mostCount$

分类讨论：

• 如果 $mostCount * 2 <= count$，则所有交换可以在这些已经相等的元素之间进行，答案为这些相等的元素下标之和
• 如果 $mostCount * 2 > count$，则交换无法只在这些相等的元素之间进行，需要与其他原本就不相等的元素进行交换，由于要使代价最小，要尽量使用下标较小的元素，并且该下标的元素不能等于 $most$，每次使用会让 $count + 1$，直至满足 $mostCount * 2 <= count$。

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