题目题意两个长度均为 n 的数组 nums 和 forbidden 可任意交换 nums 中的元素要求最终每个位置 i 满足 nums[i] ! forbidden[i] 返回最少交换次数无解返回 -1 。核心思路1. 无解判定若任意数值在 nums 和 forbidden 中的总出现次数 n根据鸽巢原理必然存在位置无法满足条件返回 -1 。2. 坏列统计统计满足 nums[i] forbidden[i] 的位置坏列总数 badSum 以及坏列中出现次数最多的数值的次数 maxBad 。3. 最小交换次数答案为 max(⌈badSum / 2⌉, maxBad)- 两两交换不同值的坏列每次消除 2 个坏列至少需要 ⌈badSum/2⌉ 次- 若某数值的坏列过多每个坏列都需要与外部好位置交换至少需要 maxBad 次。C 语言实现排序法简洁可靠c#include stdlib.hstatic int cmpInt(const void* a, const void* b) {int x *(const int*)a;int y *(const int*)b;return (x y) - (x y);}int minSwaps(int* nums, int numsSize, int* forbidden, int forbiddenSize) {int n numsSize;// 1. 合并两数组排序后统计总频率判断无解int* total (int*)malloc(2 * n * sizeof(int));for (int i 0; i n; i) total[i] nums[i];for (int i 0; i n; i) total[n i] forbidden[i];qsort(total, 2 * n, sizeof(int), cmpInt);int impossible 0;for (int i 0; i 2 * n; ) {int j i;while (j 2 * n total[j] total[i]) j;if (j - i n) {impossible 1;break;}i j;}free(total);if (impossible) return -1;// 2. 收集所有坏列nums[i] forbidden[i]int* badVals (int*)malloc(n * sizeof(int));int badSum 0;for (int i 0; i n; i) {if (nums[i] forbidden[i]) {badVals[badSum] nums[i];}}if (badSum 0) {free(badVals);return 0;}// 排序后统计坏列中最多的重复次数qsort(badVals, badSum, sizeof(int), cmpInt);int maxBad 0;for (int i 0; i badSum; ) {int j i;while (j badSum badVals[j] badVals[i]) j;if (j - i maxBad) maxBad j - i;i j;}free(badVals);int pairSwaps (badSum 1) / 2; // 向上取整return pairSwaps maxBad ? pairSwaps : maxBad;}复杂度- 时间O(n \log n)主要为两次排序的开销对于 n \le 10^5 完全满足时限。- 空间O(n)用于存储合并数组与坏列数组。需要我补充一份线性时间的拉链法哈希表版本吗