题目描述
你有两个果篮,每个果篮中有 n
个水果。给你两个下标从 0 开始的整数数组 basket1
和 basket2
,用以表示两个果篮中每个水果的成本。
你希望两个果篮相等。为此,可以根据需要多次执行下述操作:
- 选中两个下标
i
和j
,并交换basket1
中的第i
个水果和basket2
中的第j
个水果。 - 交换的成本是
min(basket1_i,basket2_j)
。
根据果篮中水果的成本进行排序,如果排序后结果完全相同,则认为两个果篮相等。
返回使两个果篮相等的最小交换成本,如果无法使两个果篮相等,则返回 -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]。重排两个数组,发现二者相等。
输入:basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出:-1
解释:可以证明无法使两个果篮相等。
限制
basket1.length == bakste2.length
1 <= basket1.length <= 10^5
1 <= basket1_i,basket2_i <= 10^9
算法
(思维题) $O(n \log n)$
- 统计出两个数组中每个数字的出现次数,如果存在某个数字的出现次数为奇数,则可以证明无法使两个数组相等。
- 接着计算出来哪些数字需要交换,以第一个数组为视角,$ask$ 记录需要换入的数字,$bid$ 记录需要换出的数字,显然 $ask$ 和 $bid$ 的长度相同。
- 将 $ask$ 和 $bid$ 排序,$ask$ 从小到大,$bid$ 从大到小进行匹配交换,交换的最小代价就是 $\min(\min(ask_i, bid_i), 2 minimum)$,其中 $minimum$ 是所有数字的最小值,可以利用这个值两次,间接的交换两个数字。
时间复杂度
- 统计的时间复杂度为 $O(n)$。
- 排序 $ask$ 和 $bid$ 的时间复杂度为 $O(n \log n)$。
- 累计答案的时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表和中间数组。
C++ 代码
#define LL long long
class Solution {
public:
LL minCost(vector<int>& basket1, vector<int>& basket2) {
const int n = basket1.size();
unordered_map<int, int> seen, seen1;
int mi = INT_MAX;
for (int i = 0; i < n; i++) {
++seen[basket1[i]]; ++seen1[basket1[i]];
++seen[basket2[i]];
mi = min(mi, basket1[i]);
mi = min(mi, basket2[i]);
}
for (const auto &[_, v] : seen)
if (v & 1)
return -1;
vector<int> ask, bid;
for (const auto &[k, v]: seen) {
if (seen1[k] < v / 2) {
for (int i = 0; i < v / 2 - seen1[k]; i++)
ask.push_back(k);
} else {
for (int i = 0; i < seen1[k] - v / 2; i++)
bid.push_back(k);
}
}
sort(ask.begin(), ask.end());
sort(bid.begin(), bid.end());
const int m = ask.size();
LL ans = 0;
for (int i = 0; i < m; i++)
ans += min(2 * mi, min(ask[i], bid[m - i - 1]));
return ans;
}
};