当前位置：首页 > news >正文

DeepSeek LeetCode 2561. 重排水果 Java实现

news 2026/5/23 0:34:58

LeetCode 2561. 重排水果

题目分析

有两个长度为 n 的数组 basket1 和 basket2，每个数组包含若干水果。每次操作可以交换两个数组中的任意水果，花费为这两个水果中较小的那个值。目标是使两个数组中的水果种类和数量完全相同（即两个数组重排后相等）。求最小总花费，如果不可能则返回 -1。

解题思路

1. 可行性判断：将所有水果放在一起统计频率。如果某种水果出现次数为奇数，则无法平分，返回 -1。
2. 目标分配：每个数组中每种水果应该有总次数的一半。
3. 找出差异：
· 对于 basket1 中多出的水果，需要交换出去
· 对于 basket2 中多出的水果，需要交换进来
4. 最小交换代价：
· 每次交换可以交换两个水果
· 最优策略是：如果存在两个水果需要交换（一个在 basket1 中多出，一个在 basket2 中多出），可以用较小代价交换它们
· 或者使用全局最小值作为"中转"来降低交换代价
5. 贪心策略：
· 收集所有需要从 basket1 换出的水果（记为 needOut）
· 收集所有需要从 basket2 换出的水果（记为 needIn）
· 对两个列表排序
· 对于每一对需要交换的水果，有两种选择：
a) 直接交换：代价 = min(a, b)
b) 通过全局最小值中转：代价 = 2 × globalMin
· 选择较小的代价

Java实现

```java
class Solution {
public long minCost(int[] basket1, int[] basket2) {
// 统计所有水果的频率
Map<Integer, Integer> freq = new HashMap<>();
for (int num : basket1) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
for (int num : basket2) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}

// 检查是否可行：每种水果出现次数必须为偶数
for (int count : freq.values()) {
if (count % 2 != 0) {
return -1;
}
}

// 计算每个数组应该有的数量
int n = basket1.length;
Map<Integer, Integer> target = new HashMap<>();
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
target.put(entry.getKey(), entry.getValue() / 2);
}

// 统计当前每个数组的水果数量
Map<Integer, Integer> count1 = new HashMap<>();
Map<Integer, Integer> count2 = new HashMap<>();
for (int num : basket1) {
count1.put(num, count1.getOrDefault(num, 0) + 1);
}
for (int num : basket2) {
count2.put(num, count2.getOrDefault(num, 0) + 1);
}

// 找出需要交换的水果
List<Integer> needOut = new ArrayList<>(); // basket1 中多出的
List<Integer> needIn = new ArrayList<>(); // basket2 中多出的

// 遍历所有水果种类
Set<Integer> allFruits = new HashSet<>(count1.keySet());
allFruits.addAll(count2.keySet());

for (int fruit : allFruits) {
int targetCount = target.getOrDefault(fruit, 0);
int c1 = count1.getOrDefault(fruit, 0);
int c2 = count2.getOrDefault(fruit, 0);

// basket1 中多出的数量
if (c1 > targetCount) {
for (int i = 0; i < c1 - targetCount; i++) {
needOut.add(fruit);
}
}
// basket2 中多出的数量
if (c2 > targetCount) {
for (int i = 0; i < c2 - targetCount; i++) {
needIn.add(fruit);
}
}
}

// 如果不需要交换
if (needOut.isEmpty()) {
return 0;
}

// 排序
Collections.sort(needOut);
Collections.sort(needIn);

// 找到全局最小值
int globalMin = Integer.MAX_VALUE;
for (int num : freq.keySet()) {
globalMin = Math.min(globalMin, num);
}

// 计算最小代价
long totalCost = 0;
int size = needOut.size();

// 只需要考虑一半的交换（因为每次交换处理一对）
// 贪心地选择代价最小的交换方式
for (int i = 0; i < size; i++) {
int a = needOut.get(i);
int b = needIn.get(size - 1 - i);

// 直接交换的代价
int directCost = Math.min(a, b);
// 通过全局最小值中转的代价
int indirectCost = 2 * globalMin;

totalCost += Math.min(directCost, indirectCost);
}

return totalCost;
}
}
```

优化版本（更简洁）

```java
class Solution {
public long minCost(int[] basket1, int[] basket2) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : basket1) freq.put(num, freq.getOrDefault(num, 0) + 1);
for (int num : basket2) freq.put(num, freq.getOrDefault(num, 0) - 1);

List<Integer> diff = new ArrayList<>();
int globalMin = Integer.MAX_VALUE;

for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
int key = entry.getKey();
int val = entry.getValue();
globalMin = Math.min(globalMin, key);

if (val % 2 != 0) return -1;

// val为正表示basket1多出，为负表示basket2多出
for (int i = 0; i < Math.abs(val) / 2; i++) {
diff.add(key);
}
}

Collections.sort(diff);

long ans = 0;
for (int i = 0; i < diff.size() / 2; i++) {
ans += Math.min(diff.get(i), 2 * globalMin);
}

return ans;
}
}
```