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实现javaclass Solution {public long minCost(int[] basket1, int[] basket2) {// 统计所有水果的频率MapInteger, 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;MapInteger, Integer target new HashMap();for (Map.EntryInteger, Integer entry : freq.entrySet()) {target.put(entry.getKey(), entry.getValue() / 2);}// 统计当前每个数组的水果数量MapInteger, Integer count1 new HashMap();MapInteger, 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);}// 找出需要交换的水果ListInteger needOut new ArrayList(); // basket1 中多出的ListInteger needIn new ArrayList(); // basket2 中多出的// 遍历所有水果种类SetInteger 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;}}优化版本更简洁javaclass Solution {public long minCost(int[] basket1, int[] basket2) {MapInteger, 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);ListInteger diff new ArrayList();int globalMin Integer.MAX_VALUE;for (Map.EntryInteger, 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;}}核心要点1. 可行性检查所有水果总出现次数必须为偶数2. 差异计算用频率差值找出需要交换的水果3. 排序贪心将最小代价的水果配对4. 中转优化使用全局最小值可以降低交换代价因为 min(a, b) ≤ 2×min 时直接交换更优否则用中转
