题目描述
你有两个果篮,每个果篮中有$n$个水果。给你两个下标从$0$开始的整数数组$basket1$和$basket2$ ,用以表示两个果篮中每个水果的成本。
你希望两个果篮相等。为此,可以根据需要多次执行下述操作:
- 选中两个下标$i$和$j$,并交换$basket1$中的第$i$个水果和$basket2$中的第$j$个水果。
- 交换的成本是$min(basket1_i,basket2_j)$。
根据果篮中水果的成本进行排序,如果排序后结果完全相同,则认为两个果篮相等。
返回使两个果篮相等的最小交换成本,如果无法使两个果篮相等,则返回$-1$。
示例$1$:
输入:basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出:1
解释:交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果,交换的成本为 1 。此时,basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组,发现二者相等。
示例$2$:
输入:basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出:-1
解释:可以证明无法使两个果篮相等。
提示:
- $basket1.length = bakste2.length$
- $1 \leq basket1.length \leq 10^5$
- $1 \leq basket1_i,basket2_i \leq 10^9$
算法
思维题
首先进行一个过滤,要想两个数组中所含数的频数相同,那每个数必须得是偶数个,否则是不可能被平分到两个数组中的。
如果数组$bastket_1$多出的数中最小值为$a$,缺少的数中最大值为$b$,直觉上来说,我们应该用$basket_1$中多余的$a$去换$bastket_2$中多余的$b$,因为这样可以使交换代价最小。因此我们可以先对两个数组进行计数,$counter$用于存储$bastket_1$和$basket_2$中所有元素的频数,$counter_1$用于存储$basket_1$中所有元素的频数,$counter_2$用于存储$basket_2$中所有元素的频数。
然后遍历$counter$中的所有键值对$(num,cnt)$
- 如果$counter_1[num]=counter_2[num]$,这个数就不用管了,直接跳过。
- 否则计算一下$delta=|counter_1[num]-counter_2[num]|$,有$\frac{delta}{2}$个$num$是需要移动的,这样才能使得$num$被平分到$basket_1$和$basket_2$中。先把$\frac{delta}{2}$个$num$存到一个数组$arr$中,供后续计算代价时使用。
这里需要注意,按照大搭配小的原则,如果需要交换的数是如下的匹配规律
a: [8,10,12,14]
b: [15,13,11,9]
我们的交换代价是$a$数组的前一半元素之和加上$b$数组的后一半元素之和,因此实际上的交换代价是$arr$排序后的前一半和。
但其实两个数除了直接交换,还存在另一种交换方式:就是以全局最小值$min$为“工具”,先用$a$中元素将$min$换过来,再用$min$把$b$中目标元素换过来,这样的交换代价就是$2min$。我们在对每一个数对进行交换时,需要比较直接交换和利用全局最小值交换这两种策略哪一种代价更小。
复杂度分析
得到$3$个频数统计表、获得$arr$数组,时间复杂度都是$O(n)$级别的。得到$arr$之后利用快速选择算法,可以在$O(n)$的时间复杂度下使得$arr$的前一半元素为最小的$\frac{arr.size()}{2}$个元素,最后遍历前一半元素就能得到最小交换代价。算法整体的时间复杂度为$O(n)$。
一共开辟了三个频数统计表,一个辅助数组$arr$,空间都是$O(n)$级别,因此算法整体的额外空间复杂度也是$O(n)$。
C++ 代码
typedef long long LL;
class Solution {
public:
long long minCost(vector<int>& basket1, vector<int>& basket2) {
unordered_map<int, LL> counter, counter1, counter2;
int mi = INT_MAX;
for(int num: basket1) {
counter[num]++;
counter1[num]++;
mi = min(mi, num);
}
for(int num: basket2) {
counter[num]++;
counter2[num]++;
mi = min(mi, num);
}
for(auto&[k, v]: counter) {
if(v&1) return -1;
}
vector<int> arr;
for(auto&[num, cnt]: counter) {
LL cnt1 = counter1.find(num) != counter1.end()? counter1[num]: 0;
LL cnt2 = counter2.find(num) != counter2.end()? counter2[num]: 0;
if(cnt1 == cnt2) continue;
int delta = abs(cnt1 - cnt2);
for(int i = 0; i < delta>>1; i++) arr.push_back(num); // 只有一半的数要换
}
int k = arr.size() >> 1;
nth_element(arr.begin(), arr.begin() + k, arr.end());
LL ans = 0;
for(int i = 0; i < k; i++) {
ans += min(mi<<1, arr[i]);
}
return ans;
}
};