C++算法：让数组不相等的最小总代价

题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的和。你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的 最小 总代价。请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。

术语

如果nums1[i] 和nums2[i]相等，是内部；否则是外部。显然，内部的数需要全部交换。

假定不同的数的数量是偶数

分析那些情况可以只内部交换，不和外包交换。下面只列出nums1和nums2中不同的元素。

猜想：除众数外，其它数都可以匹配上。

如果众数大于总数的一半，则非众数全部和众数匹配，非众数全部匹配，部分众数无法匹配，假定其为iNeedSwapOut，则其值为：众数-非众数。

如果众数小于等于总数的一半（意味着至少2种数）。假定最多的数数量为n1，次多的为n2，如果有三种数，第三多的为n3。

最多的数和次多的数匹配，也就是n1和n2的各减少1。用N1代表新的n1,N2代码新的n2.结果有三种：

• 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;
};

说明

源码和少量测试用例下载：

https://download.csdn.net/download/he_zhidan/88368465

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。

https://edu.csdn.net/course/detail/38771

我的其它课程

https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17 或Win10 VS2022 Ck++17

相关下载

算法精讲《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653