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

难度: Hard

给你两个下标从 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 <= 10⁵
1 <= nums1[i], nums2[i] <= n

Submission

运行时间: 100 ms

内存: 27.7 MB

class Solution:
    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
        ans = swap_cnt = mode_cnt = mode = 0
        cnt = [0] * (len(nums1) + 1)
        for i, (x, y) in enumerate(zip(nums1, nums2)):
            if x == y:
                ans += i
                swap_cnt += 1
                cnt[x] += 1
                if cnt[x] > mode_cnt:
                    mode_cnt = cnt[x]
                    mode = x
        for i, (x, y) in enumerate(zip(nums1, nums2)):
            if mode_cnt*2 <= swap_cnt: break
            if x != y and x != mode and y != mode:
                ans += i
                swap_cnt += 1
        return ans if mode_cnt * 2 <= swap_cnt else -1

Explain

此题解尝试通过统计在nums1和nums2中相同位置上的相同元素数量，来确定最少的交换次数。首先，初始化若干变量用于记录总的交换代价、需要交换的次数、最频繁元素的数量及其值。接着，遍历数组，对于每一对相同的元素，在nums1中统计其出现的次数，并更新如果这个元素出现的次数最多，则记录它作为mode。如果最终mode的两倍小于等于需要的交换次数，说明可以通过足够的交换避免所有冲突，返回计算的总代价；否则，如果mode元素太多，导致无法通过交换避免所有冲突，返回-1。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
        ans = swap_cnt = mode_cnt = mode = 0  # 初始化答案、交换计数、最多元素的计数和值
        cnt = [0] * (len(nums1) + 1)  # 初始化计数数组
        for i, (x, y) in enumerate(zip(nums1, nums2)):
            if x == y:
                ans += i  # 将位置i加入代价
                swap_cnt += 1  # 需要交换的次数增加
                cnt[x] += 1  # 记录该位置的元素出现次数
                if cnt[x] > mode_cnt:  # 更新最多元素的计数和值
                    mode_cnt = cnt[x]
                    mode = x
        for i, (x, y) in enumerate(zip(nums1, nums2)):
            if mode_cnt*2 <= swap_cnt: break  # 如果已经足够的交换次数，提前结束循环
            if x != y and x != mode and y != mode:
                ans += i  # 同样加入位置i的代价
                swap_cnt += 1  # 增加交换次数
        return ans if mode_cnt * 2 <= swap_cnt else -1  # 根据是否能解决所有冲突返回结果

Explore

题解通过首先遍历数组，记录下所有在相同位置上相等的元素对（x = y），并计算这些元素对的出现次数。这些元素对在后续的处理中需要被优先考虑交换，因为它们直接导致了数组元素的冲突。为了确保最小总代价，算法尝试通过找出出现次数最多的元素（即mode元素）并优先处理与这个元素相关的冲突，因为这样可以更有效地减少需要的交换次数。如果mode元素的出现次数超过一半的交换次数，则不可能通过交换解决所有冲突，这时会返回-1。

在题解中，`mode`元素指的是在需要交换的元素对中出现次数最多的元素。这个元素的重要性在于它代表了最大的冲突点。如果能够优先解决这个元素的冲突，将显著减少需要进一步交换的次数。如果`mode`元素的出现次数乘以2小于等于总的交换次数（`swap_cnt`），则通过足够的交换可以解决所有冲突，否则，如果`mode`的数量太多，即使进行所有可能的交换也无法解决所有冲突，这时算法应返回-1表示无解。

这种条件判断的逻辑基于能够通过足够的交换解决所有冲突的可能性。当`mode_cnt * 2 <= swap_cnt`时，意味着即使考虑到冲突最频繁的元素（mode元素），通过足够的交换，仍有可能解决所有元素的冲突。如果这个条件成立，算法可保证有足够的交换次数来调整数组使其符合要求。如果该条件不成立，则表示即使进行所有可能的交换也无法解决所有的冲突，因此可以提前结束处理，返回无法通过交换达到要求的结果。

是的，`cnt`数组的大小设置为`len(nums1) + 1`暗示了一个假设，即nums1中的元素值不超过数组的长度。这是一个常见的限制条件，使得可以直接使用元素值作为数组索引，从而简化问题的处理。如果实际情况中，nums1的元素值可能超过数组长度，这种方法就不再适用。在这种情况下，可以考虑使用哈希表（如Python中的字典）来记录每个元素的出现次数，虽然这可能会增加空间复杂度，但可以处理任意大小的元素值。