题目描述
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); } }
|