重排水果
难度:
标签:
题目描述
You have two fruit baskets containing n fruits each. You are given two 0-indexed integer arrays basket1 and basket2 representing the cost of fruit in each basket. You want to make both baskets equal. To do so, you can use the following operation as many times as you want:
- Chose two indices
iandj, and swap theithfruit ofbasket1with thejthfruit ofbasket2. - The cost of the swap is
min(basket1[i],basket2[j]).
Two baskets are considered equal if sorting them according to the fruit cost makes them exactly the same baskets.
Return the minimum cost to make both the baskets equal or -1 if impossible.
Example 1:
Input: basket1 = [4,2,2,2], basket2 = [1,4,1,2] Output: 1 Explanation: Swap index 1 of basket1 with index 0 of basket2, which has cost 1. Now basket1 = [4,1,2,2] and basket2 = [2,4,1,2]. Rearranging both the arrays makes them equal.
Example 2:
Input: basket1 = [2,3,4,1], basket2 = [3,2,5,1] Output: -1 Explanation: It can be shown that it is impossible to make both the baskets equal.
Constraints:
basket1.length == basket2.length1 <= basket1.length <= 1051 <= basket1[i],basket2[i] <= 109
代码结果
运行时间: 120 ms, 内存: 37.8 MB
/*
* 思路：
* 1. 首先检查两个数组长度是否相等，如果不相等，直接返回 -1。
* 2. 对两个数组分别排序，然后逐个比较，如果排序后的数组不相等，返回 -1。
* 3. 使用Stream API进行元素比较和成本计算。
* 4. 返回总交换成本。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class BasketEqualizerStream {
public int minCostToEqualizeBaskets(int[] basket1, int[] basket2) {
if (basket1.length != basket2.length) return -1;
Arrays.sort(basket1);
Arrays.sort(basket2);
boolean isEqual = IntStream.range(0, basket1.length).allMatch(i -> basket1[i] == basket2[i]);
if (!isEqual) return -1;
return IntStream.range(0, basket1.length)
.filter(i -> basket1[i] != basket2[i])
.map(i -> Math.min(basket1[i], basket2[i]))
.sum();
}
public static void main(String[] args) {
BasketEqualizerStream bes = new BasketEqualizerStream();
int[] basket1 = {4, 2, 2, 2};
int[] basket2 = {1, 4, 1, 2};
System.out.println(bes.minCostToEqualizeBaskets(basket1, basket2)); // 输出1
}
}
解释
方法:
该题解的基本思路是先使用Counter统计两个果篮中各水果的数量，然后确定可以直接匹配的水果数量并减去。剩余的水果将被放入sub_1和sub_2列表中，表示需要交换的水果。这些水果会被排序，然后一对一匹配进行最小成本交换。如果在某种水果的个数不是偶数，那么返回-1，因为不能完全通过交换使得两个篮子中水果相等。交换成本取决于两个水果中较小的那个的成本。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在计算两个列表中水果的差异时使用`b2[k] > 0`条件，这是怎样帮助确定需要交换的水果数量的？
▷🦆
解释中提到如果水果的个数是奇数就返回-1，为什么水果个数的奇偶性会影响到交换的可能性？
▷🦆
在排序和匹配剩余水果时，为什么选择将sub_1和sub_2列表排序？这种排序对最终的交换成本计算有何影响？
▷🦆
代码中有一处判断`if sub_1[l] < sub_2[r]`，这里的逻辑是基于什么考虑？它如何确保交换成本被最小化？
▷