你有两个果篮，每个果篮中有 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
首先，把两个数组中都有的数去掉，那么每个剩余数字的出现次数必须为偶数。这可以用哈希表来统计。
设处理后的剩余数组分别 a 和 b。
贪心地想，如果要交换 a 中最小的数，那么找一个 b 中最大的数是最合适的；对于 b 中最小的数也同理。
那么把 a 从小到大排序，b 从大到小排序，两两匹配。
但是，还有一种方案。
把 basket}_1 和 basket}_2 中的最小值 mn 当作「工具人」，对于 a[i] 和 b[i] 的交换，可以分别和 mn 交换一次，就相当于 a[i] 和 b[i] 交换了。
因此每次交换的代价为
\min(a[i], b[i], 2\cdot\textit{mn})
累加代价，即为答案。
上式也表明，如果工具人也在需要交换的数字中，那么它的最小代价必然是和其他数交换，不会发生工具人和工具人交换的情况。
设 m 为 a 的长度。代码实现时，由于 \min(a[i], b[i]) 的数字都在 a 的某个前缀与 b 某个后缀中，而剩下没有选的数（a 的后缀和 b 的前缀）不比这 m 个数小，所以取出的数一定是这 2m 个数中最小的 m 个数。
更详细的证明：设选了 a[0],\cdots,a[i] 和 b[i+1],\cdots,b[m-1]，由于 a[i+1]\ge b[i+1] 且 a[i+1] \ge a[i]，所以 a[i+1] \ge 任意已选数字，进而推出 a[i+2],\cdots,a[m-1] 都是大于等于任意已选数字的；对于 b[i] 和 b[i-1],\cdots,b[0] 同理。所以剩下没有选的数字都比已选数字大，进而说明已选数字是这 2m 个数中最小的 m 个数。
那么可以直接把 a 和 b 拼起来，从小到大排序后，遍历前一半的数即可（排序可以用快速选择代替，见 C++）。
附：视频讲解
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
| 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])
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 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;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 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;
}
};
|
[sol1-Go]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 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 }
|
复杂度分析
- 时间复杂度：O(n\log n) 或 O(n)，其中 n 为 basket}_1 的长度。用快速选择可以做到 O(n)（见 C++）。
- 空间复杂度：O(n)。
