LeetCode 题解工作台
让数组不相等的最小总代价
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。 每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。 你的目标是对于所有的 0 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们先同时遍历数组 `nums1` 和 `nums2`，统计相同位置上的值相同的个数 `same`，这些位置上的值必须交换，因此，将这些位置下标累加到答案中。另外，用数组或哈希表 `cnt` 统计这些相同值的出现次数。 如果所有相同值的出现次数均不超过 `same` 的一半，那么意味着，我们可以在其内部，通过两两交换，使得对应位置上的值不同，而这些交换，已经在上面累加下标时计入了答案中了，无需额外…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你两个下标从 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.length1 <= n <= 1051 <= nums1[i], nums2[i] <= n
解题思路
方法一：贪心
我们先同时遍历数组 nums1 和 nums2，统计相同位置上的值相同的个数 same，这些位置上的值必须交换，因此，将这些位置下标累加到答案中。另外，用数组或哈希表 cnt 统计这些相同值的出现次数。
如果所有相同值的出现次数均不超过 same 的一半，那么意味着，我们可以在其内部，通过两两交换，使得对应位置上的值不同，而这些交换，已经在上面累加下标时计入了答案中了，无需额外的代价。否则，如果某个值的出现次数超过 same 的一半，那么对于这个值就是多出的个数，我们需要在数组的其他位置上找到合适的，进行交换。这里我们可以直接遍历一遍数组得出。
如果最终还有剩余位置未能交换，说明无法达成目标，返回 即可，否则返回答案。
时间复杂度 ，空间复杂度 。其中 是数组 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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on scanning the arrays and resolving conflicts via hash lookups and sorting indices, typically O(n log n) for large n. Space complexity arises from the hash table to count frequencies, O(n). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you notice repeated values that block a solution?
- question_mark
How can you efficiently identify which indices to swap first?
- question_mark
What is the minimal cost approach for handling multiple conflicts?
常见陷阱
外企场景- error
Failing to account for repeated values that exceed half the array length, making a solution impossible.
- error
Swapping indices without considering combined cost can produce non-optimal total cost.
- error
Ignoring updates to the hash table after each swap can cause incorrect conflict tracking.
进阶变体
外企场景- arrow_right_alt
Return the actual sequence of swaps instead of just the total cost.
- arrow_right_alt
Allow swaps between nums1 and nums2 instead of only within nums1.
- arrow_right_alt
Extend to multiple arrays where each must differ from all others at every index.