DeepSeek LeetCode 3785. 避免禁用值的最小交换次数 Java实现
根据我的深入分析，LeetCode 3785: Minimum Swaps to Avoid Forbidden Values 的正确解法是使用 `max(⌈badPairsSum / 2⌉, maxBadPairs)` 公式，但需要注意一个已知的边界情况争议。
问题分析
核心思路：
1. 坏位置 (Bad Position)：`nums[i] == forbidden[i]` 的位置
2. 频率检查：如果某个值在 `nums` 和 `forbidden` 中出现总次数超过 `n`，则不可能完成，返回 `-1`
3. 关键观察：每次交换可以修复最多 2 个坏位置
正确 Java 实现
```java
import java.util.*;
class Solution {
public int minSwaps(int[] nums, int[] forbidden) {
int n = nums.length;
// Step 1: 频率检查 - 判断是否有解
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
for (int x : forbidden) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
for (int count : freq.values()) {
if (count > n) {
return -1;
}
}
// Step 2: 统计坏位置
Map<Integer, Integer> badPairs = new HashMap<>();
int badPairsSum = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == forbidden[i]) {
badPairs.put(nums[i], badPairs.getOrDefault(nums[i], 0) + 1);
badPairsSum++;
}
}
if (badPairsSum == 0) {
return 0;
}
// Step 3: 找到最大坏位置数
int maxBadPairs = 0;
for (int count : badPairs.values()) {
maxBadPairs = Math.max(maxBadPairs, count);
}
// Step 4: 核心公式
// ⌈badPairsSum / 2⌉ = (badPairsSum + 1) / 2
return Math.max((badPairsSum + 1) / 2, maxBadPairs);
}
}
```
公式解释
`max(⌈badPairsSum / 2⌉, maxBadPairs)` 的含义：
1. `⌈badPairsSum / 2⌉`：每次交换最多修复 2 个坏位置，所以至少需要这么多交换
2. `maxBadPairs`：如果某个值出现了 `maxBadPairs` 次坏位置，这些位置之间不能互相交换（交换相同值无意义），必须与其他值交换。如果其他坏位置不够，就需要与好位置交换
关于已知争议
GitHub 上有用户报告了一个反例：
- `nums = [6,6,8,8,8,9,9,9,4,4]`
- `forbidden = [6,6,8,8,8,9,9,9,6,6]`
声称公式给出 4 但实际需要 5。但经过我的详细验证，这个反例实际上可以用 4 次交换完成：
```
Swap 1: pos 0(6) ↔ pos 2(8) → [8,6,6,8,8,9,9,9,4,4]
Swap 2: pos 1(6) ↔ pos 5(9) → [8,9,6,8,8,6,9,9,4,4]
Swap 3: pos 3(8) ↔ pos 6(9) → [8,9,6,9,8,6,8,9,4,4]
Swap 4: pos 4(8) ↔ pos 7(9) → [8,9,6,9,9,6,8,8,4,4]
```
最终所有位置都满足 `nums[i] != forbidden[i]`，所以公式是正确的。
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)（用于哈希表）
这个解法简洁高效，是 LeetCode 官方期望的解法。