LC-6345.重排水果

题目描述

leetcode 困难题

你有两个果篮,每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ,用以表示两个果篮中每个水果的成本。

你希望两个果篮相等。为此,可以根据需要多次执行下述操作:

选中两个下标 i 和 j ,并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
交换的成本是 min(basket1i,basket2j) 。
根据果篮中水果的成本进行排序,如果排序后结果完全相同,则认为两个果篮相等。

返回使两个果篮相等的最小交换成本,如果无法使两个果篮相等,则返回 -1 。

示例1:

1
2
3
4
输入: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] 。重排两个数组,发现二者相等。

提示1:

1
2
3
basket1.length == bakste2.length
1 <= basket1.length <= 10^5
1 <= basket1i,basket2i <= 10^9

贪心

设两个果篮中的所有的水果种类分别为 $a[1],a[2]…a[i]$ ,这些水果在两个果篮中的数量分别为 $cnt1[1]…cnt1[i]$ 、 $cnt2[1]…cnt2[i]$ 。

显然对于所有水果种类,均需要满足 $cnt1[i] + cnt2[i] \% 2 == 0$,否则说明某种水果总数量为奇数,无论怎么交换,都无法平均的分配到两个果篮中,并且需要交换的水果显然只有 $cnt1[i] != cnt2[i]$ 的。因此我们可以先预处理出这部分水果种类,设其为 $b[1]…b[i]$ ,需要交换的次数显然为 $abs(cnt[1] - cnt[2]) / 2$,并且为了使成本最低,我们可以堆化这部分水果,每次弹出最小的成本即可。

需要注意一种特殊情况,例如 case :

[84,80,43,8,80,88,43,14,100,88]

[32,32,42,68,68,100,42,84,14,8]

在该用例中,堆中需要交换的水果为

[32, 43, 42, 88, 68, 80]

按照上面的分析,此时会取最小的成本 $32$ ,考虑有没有更低成本的做法,我们可以取果篮中最小成本的水果,也就是 $8$ ,通过该水果作为中介进行两次交换,来将我们需要交换的水果放到目标果篮中,此时成本为 $8 *2 = 16$ 。所以当果篮中最小成本水果的成本 * 2 依然小于堆顶的水果成本时,可以利用最小成本水果进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public long minCost(int[] basket1, int[] basket2) {
Function<int[], Map<Integer, Integer>> fun = arr -> Arrays.stream(arr).boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.summingInt(e -> 1)));;
Map<Integer, Integer> cnt1 = fun.apply(basket1), cnt2 = fun.apply(basket2);
List<Integer> all = Stream.concat(cnt1.keySet().stream(), cnt2.keySet().stream()).distinct().toList();
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int item : all) {
int sub = Math.abs(cnt1.getOrDefault(item, 0) - cnt2.getOrDefault(item, 0));
if ((sub & 1) == 1) {
return -1;
}
IntStream.generate(() -> item).limit(sub / 2).forEach(minHeap::offer);
}
int min = all.stream().mapToInt(Integer::valueOf).min().orElseThrow() * 2;
return IntStream.range(0, minHeap.size() / 2).boxed().reduce(0L,
(ans, e) -> ans + Math.min(min, minHeap.poll()), Long::sum);
}
}

相同的思路,另一种写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public long minCost(int[] basket1, int[] basket2) {
Function<int[], Map<Integer, Integer>> fun = arr -> Arrays.stream(arr).boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.summingInt(e -> 1)));;
Map<Integer, Integer> cnt1 = fun.apply(basket1), cnt2 = fun.apply(basket2);
List<Integer> all = Stream.concat(cnt1.keySet().stream(), cnt2.keySet().stream()).distinct().toList();
Function<Integer, Integer> getSize = i -> Math.abs(cnt1.getOrDefault(i, 0) - cnt2.getOrDefault(i, 0));
if (all.stream().anyMatch(i -> (getSize.apply(i) & 1) == 1)) {
return -1;
}
int min = all.stream().mapToInt(Integer::valueOf).min().orElseThrow() * 2;
List<Integer> sort = all.stream().flatMapToInt(i -> IntStream.generate(() -> i).limit(getSize.apply(i) / 2))
.boxed().sorted().toList();
return IntStream.range(0, sort.size() / 2).boxed().reduce(0L,
(ans, e) -> ans + Math.min(min, sort.get(e)), Long::sum);
}
}

LC-6345.重排水果
https://wecgwm.github.io/2023/02/06/LC-6345-重排水果/
作者
yichen
发布于
2023年2月6日
许可协议