class Solution {
public:
long long minCost(vector<int>& basket1, vector<int>& basket2) {
}
};
6345. 重排水果
你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的成本。
你希望两个果篮相等。为此，可以根据需要多次执行下述操作：
i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。min(basket1i,basket2j) 。根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。
返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -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.length1 <= basket1.length <= 1051 <= basket1i,basket2i <= 109原站题解
golang 解法, 执行用时: 168 ms, 内存消耗: 13.2 MB, 提交时间: 2023-02-06 10:39:36
func minCost(basket1, basket2 []int) (ans int64) {
cnt := map[int]int{}
for i, x := range basket1 {
cnt[x]++
cnt[basket2[i]]--
}
mn, a := math.MaxInt, []int{}
for x, c := range cnt {
if c%2 != 0 {
return -1
}
mn = min(mn, x)
for c = abs(c) / 2; c > 0; c-- {
a = append(a, x)
}
}
sort.Ints(a) // 也可以用快速选择
for _, x := range a[:len(a)/2] {
ans += int64(min(x, mn*2))
}
return
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 160 ms, 内存消耗: 83.9 MB, 提交时间: 2023-02-06 10:39:06
class Solution {
public:
long long minCost(vector<int> &basket1, vector<int> &basket2) {
unordered_map<int, int> cnt;
for (int i = 0; i < basket1.size(); ++i) {
++cnt[basket1[i]];
--cnt[basket2[i]];
}
int mn = INT_MAX;
vector<int> a;
for (auto [x, c] : cnt) {
if (c % 2) return -1;
mn = min(mn, x);
for (c = abs(c) / 2; c > 0; --c)
a.push_back(x);
}
long ans = 0;
nth_element(a.begin(), a.begin() + a.size() / 2, a.end()); // 快速选择
for (int i = 0; i < a.size() / 2; ++i)
ans += min(a[i], mn * 2);
return ans;
}
};
java 解法, 执行用时: 34 ms, 内存消耗: 60.6 MB, 提交时间: 2023-02-06 10:38:45
class Solution {
public long minCost(int[] basket1, int[] basket2) {
var cnt = new HashMap<Integer, Integer>();
for (int i = 0; i < basket1.length; ++i) {
cnt.merge(basket1[i], 1, Integer::sum);
cnt.merge(basket2[i], -1, Integer::sum);
}
int mn = Integer.MAX_VALUE;
var a = new ArrayList<Integer>();
for (var e : cnt.entrySet()) {
int x = e.getKey(), c = e.getValue();
if (c % 2 != 0) return -1;
mn = Math.min(mn, x);
for (c = Math.abs(c) / 2; c > 0; --c)
a.add(x);
}
long ans = 0;
a.sort((x, y) -> x - y); // 也可以用快速选择
for (int i = 0; i < a.size() / 2; ++i)
ans += Math.min(a.get(i), mn * 2);
return ans;
}
}
python3 解法, 执行用时: 216 ms, 内存消耗: 36.9 MB, 提交时间: 2023-02-06 10:38:26
'''
贪心+构造，把两个篮子里最小的数作为中介工具
'''
class Solution:
def minCost(self, basket1: List[int], basket2: List[int]) -> int:
cnt = Counter()
for x, y in zip(basket1, basket2):
cnt[x] += 1
cnt[y] -= 1
mn = min(cnt)
a = []
for x, c in cnt.items():
if c % 2: return -1
a.extend([x] * (abs(c) // 2))
a.sort() # 也可以用快速选择
return sum(min(x, mn * 2) for x in a[:len(a) // 2])