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则不可能完成返回 -13. 关键观察每次交换可以修复最多 2 个坏位置正确 Java 实现javaimport java.util.*;class Solution {public int minSwaps(int[] nums, int[] forbidden) {int n nums.length;// Step 1: 频率检查 - 判断是否有解MapInteger, 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: 统计坏位置MapInteger, 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) / 2return 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 官方期望的解法。