题目
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的和。你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的 最小 总代价。请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。
术语
如果nums1[i] 和nums2[i]相等，是内部；否则是外部。显然，内部的数需要全部交换。
假定不同的数的数量是偶数
分析那些情况可以只内部交换，不和外包交换。下面只列出nums1和nums2中不同的元素。
|
nums1 |
nums2 |
交换过程 |
能否能内部交换 |
|
[1,2] |
[1,2] |
[2,1] |
能 |
|
[1,2,2,2] |
[1,2,2,2] |
[2,1,2,2] |
不能 |
|
[1,2,3,4] |
[1,2,3,4] |
[2,1,3,4][2,1,4,3] |
能 |
|
[1,1,2,3] |
[1,1,2,3] |
[2,1,1,3][2,3,1,1] |
能 |
|
[1,1,2,2] |
[1,1,2,2] |
[2,1,1,2][2,2,1,1] |
能 |
猜想：除众数外，其它数都可以匹配上。
如果众数大于总数的一半，则非众数全部和众数匹配，非众数全部匹配，部分众数无法匹配，假定其为iNeedSwapOut，则其值为：众数-非众数。
如果众数小于等于总数的一半（意味着至少2种数）。假定最多的数数量为n1，次多的为n2，如果有三种数，第三多的为n3。
最多的数和次多的数匹配，也就是n1和n2的各减少1。用N1代表新的n1,N2代码新的n2.结果有三种：
|
|
转换前 |
转换后 |
|
情况一 |
[1,2] |
[] |
|
情况二 |
[1,2,3,4] |
[3,4] |
|
[1,1,2,2,3,3] |
[3,3,1,2] |
|
|
[1,1,1,2,2,2,3,3,3,4] |
[3,3,3,1,1,2,2,4] |
|
|
情况三 |
[1,1,2,3] |
[1,3] |
- N1和N2都为0，匹配结束。由于和是偶数，每次匹配和减少2，最终一定为成为0。
- N1为n1-1，由于2*n1 <= sum ，所以 2*(n1-1) <= sum-2。 匹配后，仍然符合：众数小于等于总数的一半。
- N1为n3，前提条件 n1和n2和n3相等，且都大于0。其和至少为n3*3-2。假的2*n3 > n3*3-2，则0 >n3-2，即n < 2。
n1为1时，此时有偶数个数量为1的种类，任意匹配都符合题意。
结论
如果众数小于等于总数的一半，则所有的数都可以内部匹配。如果众数大于总数的一半，则部分众数需要在外部匹配。
如果不同数的数量是奇数
由于是奇数，众数的数量不会等于总数的一半。
如果众数小于总数的一半
用C++的整数表示就是：modeCount <= iNotSameCount/2 ，推论：至少有3个数。n1,n2,n3各取一个数，余下的数，符合偶数且众数小于等于总数的一半。这三个数，至少有一个数，和当前的nums1[0]、nums2[i]不同，假定为x,另外两个数分别为y1,y2。分三步：一，先交换除x,y1,y2外的数。二，再交换y1,y2。三，交换nums1[i]和x。由于x和y1 y2 原始nums1[i]和nums2[i]都不同，所以完成第二步后nums1[0]和nums2[0]一定和x不同。
如果众数大于总数的一半
多出的部分外部匹配。其它内部匹配。
结论
如果众数小于等于总数的一半（整除2），则全部内交换。否则需要外部交换，需要的交换次数可以用统一的公式。
int iNeedSwapOut = max(0,modeCount - (iNotSameCount - modeCount));
代码结构
代码分三部分。
- 计算内部的数量，需要交换的数的数量。内部交换的总代价。
- 计算需要交换的数的众数（数量最多的数）。
- 计算外部交换的总代价。
-
代码
class Solution {
public:
long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
m_c = nums1.size();
int iNotSameCount = 0;
long long llRet = 0;
std::unordered_map<int, int> mNotSameNum;
for (int i = 0; i < m_c; i++)
{
if (nums1[i] != nums2[i])
{
continue;
}
llRet += i;
mNotSameNum[nums1[i]]++;
iNotSameCount++;
}
if (mNotSameNum.empty())
{
return 0;
}
//如果众数不超过一半（意味着至少2个数)，如果是偶数，内部就可以交换。
//如果是奇数，至少有一个和nums2[0]不同。
//求众数和众数出现的数量
int mode = -1;
int modeCount = 0;
for (const auto& [v, n] : mNotSameNum)
{
if (n > modeCount)
{
mode = v;
modeCount = n;
}
}
//除众数外，其它数都可以内部交换，非众数都可以和众数交换
int iNeedSwapOut = max(0,modeCount - (iNotSameCount - modeCount));
for (int i = 0; (i < m_c)&& iNeedSwapOut; i++)
{//必须从小到循环，这样才能代价最小
if (nums1[i] == nums2[i])
{//已经是内部
continue;
}
if ((mode == nums1[i]) || (mode == nums2[i]))
{//不能和众数交换，或者i或交换的元素相等
continue;
}
iNeedSwapOut--;
llRet += i;
}
return iNeedSwapOut ? -1 : llRet ;
}
int m_c;
};
