第 178 场双周赛Q3：101015. 通过交换使数组相等的最小花费

题目链接：101015. 通过交换使数组相等的最小花费（中等）

算法原理：

解法：哈希表

170ms击败33.86%

时间复杂度O(N)

由于组内交换免费，那么我们就无需关注组内交换了，仅需关注跨组交换即可

（1）思考一下：什么时候nums1和nums2才能相等？所有元素都出现偶数次的时候

因此我们先用哈希表hash统计nums1和nums2中各数字出现的次数，只要有一个不是偶数，那么两数组不管怎么交换都不可能相等，直接返回-1

（2）那么在跨组交换花费1的情况下如何使花费最小呢？

可以通过刚才统计的hash，找到该数字在nums1中本应存在的次数，多出的移出给nums2，缺少的找nums2要呗

①因此我们需要用hash1和hash2分别存储nums1和nums2中各数字出现的次数

②再找到该数字应在本数组出现的次数need

③计算差值 diff=hash1.getOrDefault(x,0)-need，如果diff>0，说明数字x在nums1需要移出，需要花费1与nums2交换

④细节：移入=移出，因此仅需统计一个即可，由于nums1和nums2两数组长度相同，当nums1移出3个2时，nums2必然会移入给nums1缺少的3个3，因此移入和移出仅需记录一个即可

优化

80ms击败94.49%

时间复杂度O(N)

我们也可以避免统计nums1和nums2中各数字出现次数，直接用一个差值哈希表代替：

diff[x]:x元素在nums1中出现次数-在nums2出现次数

那么要想让两数组相等，就必须保证diff[x]=0，优化前的思路转化为：

①返回-1的时机：x为奇数，肯定无法交换后两数组都有

②累加原理：

拿nums1=[1,1,2]，nums2=[2,2,2]举例

统计完diff后，diff[1]=2，diff[2]=-2，因为移入=移出，因此我们仅需处理diff[x]>0或diff[x]<0的情况即可，我们选择处理diff[x]>0，那么此时diff[1]=2，但实际上我们仅需交换1次即可解决，因为这一次交换影响的时，移出的1导致nums1中的1次数-1，但同时nums2中1的次数+1，从而导致diff=0，因此累加时d需要除以2：ret+=d>0?d/2:0;

注意不要绕晕：

①仅处理diff[x]>0或diff[x]<0：移出的1的个数=移入的2的个数，因此仅需处理一半即可

②累加时d需要除以2：nums1移出1后，nums2获得的1会与nums1持平，因此除以2

进阶优化

45ms击败97.64%

时间复杂度O(N)

我们也可以用数组来代替HashMap，因为数组会更快一些，我们仅需找到nums1和nums2的最大值，按这个最大值来开对应空间大小的int数组即可

Java代码：

class Solution { public int minCost(int[] nums1, int[] nums2) { int n=nums1.length; Map<Integer,Integer> hash=new HashMap<>(); Map<Integer,Integer> hash1=new HashMap<>(); Map<Integer,Integer> hash2=new HashMap<>(); for(int x:nums1){ hash.merge(x,1,Integer::sum); hash1.merge(x,1,Integer::sum); } for(int x:nums2){ hash.merge(x,1,Integer::sum); hash2.merge(x,1,Integer::sum); } for(int val:hash.values()) if(val%2!=0) return -1; int ret=0; for(int x:hash.keySet()){ int need=hash.get(x)/2; int diff=hash1.getOrDefault(x,0)-need; //交换只累加一次，因为：移入=移出 ret+=diff>0?diff:0; } return ret; } }

class Solution { //优化 public int minCost(int[] nums1, int[] nums2) { int n=nums1.length; //diff[x]:x元素在nums1中出现次数-在nums2出现次数 Map<Integer,Integer> diff=new HashMap<>(); for(int x:nums1) diff.merge(x,1,Integer::sum);//diff[x]++ for(int x:nums2) diff.merge(x,-1,Integer::sum);//diff[x]-- int ret=0; for(int d:diff.values()){ if(d%2!=0) return -1; ret+=d>0?d/2:0; } return ret; } }

class Solution { //进阶优化：数组代替哈希表 public int minCost(int[] nums1, int[] nums2) { int n=nums1.length,max=0; for(int x:nums1) max=Math.max(max,x); for(int x:nums2) max=Math.max(max,x); //diff[x]:x元素在nums1中出现次数-在nums2出现次数 int[] diff=new int[max+1]; for(int x:nums1) diff[x]++; for(int x:nums2) diff[x]--; int ret=0; for(int d:diff){ if(d%2!=0) return -1; ret+=d>0?d/2:0; } return ret; } }