这道题是经典的贪心算法问题。我们需要通过交换 nums 中的元素使得对于任意下标 i都有 nums[i] ! forbidden[i]。核心思路分析1. 判断无解情况鸽巢原理如果某个数字 val 在 nums 和 forbidden 两个数组中出现的总次数大于数组长度 n那么根据鸽巢原理必然至少有一列上下都是 val此时无论如何交换都无法满足条件直接返回 -1。2. 统计“坏位置”Bad Pairs遍历数组找出所有 nums[i] forbidden[i] 的位置。我们将这些位置上冲突的值收集起来记为坏值列表。3. 贪心计算最小交换次数设坏位置的总数为 bad_sum其中出现次数最多的某个坏值的频次为 max_bad。- 情况一某个坏值占据了绝对多数即 max_bad bad_sum - max_bad等价于 max_bad * 2 bad_sum。这意味着我们必须频繁地将这个高频坏值与其他“好位置”非坏位置进行交换。每次交换最多只能消除 1 个坏位置因此需要的最小交换次数就是 max_bad。- 情况二坏值分布相对均匀即 max_bad * 2 bad_sum。此时我们可以优先将两个不同的坏值进行交换每次操作可以消除 2 个坏位置。因此消除所有坏位置所需的最小交换次数为 ceil(bad_sum / 2)即 (bad_sum 1) // 2。综合以上两种情况最小交换次数即为 max((bad_sum 1) // 2, max_bad)。Python 代码实现from typing import Listfrom collections import defaultdictclass Solution:def minSwaps(self, nums: List[int], forbidden: List[int]) - int:n len(nums)# 1. 统计 nums 和 forbidden 中每个数字的总出现次数total_freq defaultdict(int)for i in range(n):total_freq[nums[i]] 1total_freq[forbidden[i]] 1# 2. 鸽巢原理如果某个数字总出现次数超过 n则无解for freq in total_freq.values():if freq n:return -1# 3. 统计“坏位置”nums[i] forbidden[i]及其对应值的频次bad_freq defaultdict(int)bad_sum 0 # 坏位置的总数max_bad 0 # 单个坏值出现的最大频次for i in range(n):if nums[i] forbidden[i]:bad_freq[nums[i]] 1bad_sum 1max_bad max(max_bad, bad_freq[nums[i]])# 4. 贪心计算最小交换次数# 如果最大频次的坏值超过了坏值总数的一半则需要 max_bad 次交换# 否则每次可以消除两个坏值需要 ceil(bad_sum / 2) 次交换return max((bad_sum 1) // 2, max_bad)复杂度分析* 时间复杂度O(n)其中 n 是数组的长度。我们只需要遍历数组常数次来进行统计和计算。* 空间复杂度O(n)主要用于存储哈希表字典中不同数字的频次信息。需要我用几组测试用例帮你验证一下代码的正确性吗
