本文涉及知识点
贪心 分类讨论
LeetCode2499. 让数组不相等的最小总代价
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。
每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。
你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的 最小 总代价。
请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。
示例 1：
输入：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
输出：10
解释：
实现目标的其中一种方法为：
- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法，但是无法得到代价和小于 10 的方案。
示例 2：
输入：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
输出：10
解释：
实现目标的一种方法为： - 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。
- 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。
总代价为 10 ，是所有方案中的最小代价。
示例 3：
输入：nums1 = [1,2,2], nums2 = [1,2,2]
输出：-1
解释：
不管怎么操作，都无法满足题目要求。
所以返回 -1 。
提示：
n == nums1.length == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= n
分类讨论
能否不相等
cnt[x]记录x在nums1和nums2中出现的总次数。cnt[x]取最大值对应的x是x1(众数）。
如果cnt[x1] > n，则一定无法不相等。nums1[i]和nums2[i]只能有一个是x，而i的取值范围是[0,n)共n种可能，顶多存放n个x。
如果cnt[x1]==n ，nums1[i]或nums2[i]中的一个等于x，另外一个不为x。故：一定能不相等。
下面来证明：cnt[x1] < n，一定能不相等。证明一。
x1是众数，说明其它数<=cnt[x1] 2个x1 < 2*n，所以至少3个数。任选另外两个数各删除一个。众数不变（x1没减少，其它数减少少或不变)，n–，经过优先次数n一定会等于x1。
何种顺序交换
cnt[x] 记录nums1[i]==nums2[i]==x 的数量。
令x = x1时cnt[x]取最大值。令sum = ∑ x ≠ x 1 ( c n t [ x ] ) \sum_{x\neq x1}(cnt[x])∑x=x1(cnt[x])
一，cnt[x1] <= sum
如果总数量是偶数：按证明一的方法两两交换。
如果总是是奇数：说明至少3个数，总有一个数不等于nums1[0]和nums2[0]，用这个数和下标0换。
二，cnt[x1] <= sum
sum个x按上述方式处理。n1 = cnt[x1]- sum个x 和符合以下条件的最小下标换。
1,没交换过，交换过的nums1[i]或nums2[i]至少一个是x1。
2，nums1[i]和nums2[i]不等于x。
代码
核心代码
class Solution { public: long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) { { unordered_map<int, int> mNumCount; for (const auto& n : nums1) { mNumCount[n]++; } for (const auto& n : nums2) { mNumCount[n]++; } for (const auto& [tmp, cnt] : mNumCount) { if (cnt > nums1.size()) { return -1; } } } unordered_map<int, int> mNumCount; long long ans = 0; for (int i = 0; i < nums1.size(); i++) { if (nums1[i] == nums2[i]) { mNumCount[nums1[i]]++; ans += i; } } int x1 = -1, ctn1 = 0,total=0; for (const auto& [num, cnt] : mNumCount) { if (cnt > ctn1) { x1 = num; ctn1 = cnt; } total += cnt; } int iNeedChange = ctn1 - (total - ctn1); if (iNeedChange <= 0) { return ans; } for (int j = 0; j < nums1.size(); j++) { if ((nums1[j] == nums2[j]) || (nums1[j] == x1) || (nums2[j] == x1)) { continue; } ans += j; if (--iNeedChange <= 0) { return ans; } } return -1; } int m_c; };
优化
前面的判断可以省略.
class Solution { public: long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> mNumCount; long long ans = 0; for (int i = 0; i < nums1.size(); i++) { if (nums1[i] == nums2[i]) { mNumCount[nums1[i]]++; ans += i; } } int x1 = -1, ctn1 = 0,total=0; for (const auto& [num, cnt] : mNumCount) { if (cnt > ctn1) { x1 = num; ctn1 = cnt; } total += cnt; } int iNeedChange = ctn1 - (total - ctn1); if (iNeedChange <= 0) { return ans; } for (int j = 0; j < nums1.size(); j++) { if ((nums1[j] == nums2[j]) || (nums1[j] == x1) || (nums2[j] == x1)) { continue; } ans += j; if (--iNeedChange <= 0) { return ans; } } return -1; } int m_c; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector nums1, nums2; { Solution sln; nums1 = { 1, 2, 3, 4, 5 }, nums2 = { 1, 2, 3, 4, 5 }; auto res = sln.minimumTotalCost(nums1, nums2); Assert(10, res); } { Solution sln; nums1 = { 2,2,2,1,3 }, nums2 = { 1,2,2,3,3 }; auto res = sln.minimumTotalCost(nums1, nums2); Assert(10, res); } { Solution sln; nums1 = { 1,2,2 }, nums2 = { 2,2,1 }; auto res = sln.minimumTotalCost(nums1, nums2); Assert(-1, res); } }
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
