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

【Leetcode】2561. 重排水果

news 2025/8/3 18:06:19

文章目录

题目
思路
- - 步骤1: 差异计算与可行性检查
  - 步骤2: 收集需要移动的水果
  - 步骤3: 贪心配对与成本计算（核心优化）
  - 整体优势
代码
- C++
- Java
- Python
复杂度分析
- 时间复杂度
- 空间复杂度
结果
总结

题目

题目链接🔗

你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2，用以表示两个果篮中每个水果的交换成本。你想要让两个果篮相等。为此，可以根据需要多次执行下述操作：

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

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

示例 1：

输入：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]。重排两个数组，发现二者相等。

示例 2：

输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出：-1
解释：可以证明无法使两个果篮相等。

提示：

basket1.length == basket2.length
1 <= basket1.length <= 10^5
1 <= basket1[i], basket2[i] <= 10^9

思路

这个问题本质上是平衡两个果篮中水果分布的最小成本问题。我们可以通过交换操作“移动”水果，使两个篮子的排序后内容相同。优化思路基于贪心算法，重点在差异计算和配对策略上。

步骤1: 差异计算与可行性检查

使用一个哈希表直接计算每个水果在basket1和basket2的数量差值（diff = count1 - count2）。
检查可行性：对于每种水果，diff必须是偶数（因为需要平衡diff/2个实例）。如果任何diff不是偶数，返回-1。这确保总数量为偶数，且可平衡。
优势：简化了原先的合并总数量步骤，直接操作差值，减少计算开销。

步骤2: 收集需要移动的水果

对于diff > 0的水果，从basket1“移出”diff/2个实例（放入swap1列表，表示basket1的多余供给）。
对于diff < 0的水果，从basket2“移出”-diff/2个实例（放入swap2列表，表示basket2的多余供给）。
同时，找到全局最小成本水果globalMin，用于潜在的中转交换。

步骤3: 贪心配对与成本计算（核心优化）

将swap1升序排序（从小到大），swap2降序排序（从大到小）。
逐一配对：对于每个pair (a = swap1[i], b = swap2[i])，成本 = min(min(a, b), 2 * globalMin)。
- 直接交换成本：min(a, b)。
- 中转交换成本：2 * globalMin（使用最小水果作为媒介，进行两次交换）。
为什么这种配对是最优的？
- 这是一种贪心策略：将最小供给 (小a) 与最大需求 (大b) 配对，确保min(a, b) 倾向于小值，同时中转选项覆盖高成本情况。
- 证明：假设我们有供给序列S和需求序列D，成本函数f(x, y) = min(min(x,y), 2*min)。反向排序配对最小化总成本，因为它优先让小值决定直接成本，或用中转“封顶”高成本（类似于分配问题中的贪心证明：排序后配对能最小化sum of min）。
- 如果随机配对，可能导致小值与小值配对（浪费低成本机会）或大值与大值配对（被迫支付高直接成本）。此策略确保全局最小。
边缘情况：如果swap1和swap2长度不相等（理论上不会，因为总diff平衡），或所有diff=0（成本0）。

整体优势

时间复杂度O(n + m log m)，m为移动数量（<= n/2），适合n=1e5。
思路简洁，具有扩展性（如多中转选项可升级为优先队列）。

代码

C++

#include <bits/stdc++.h>
using namespace std;class Solution {
public:long long minCost(vector<int>& basket1, vector<int>& basket2) {unordered_map<int, int> cnt;int n = basket1.size();// 步骤1: 统计差值for (int i = 0; i < n; ++i) {cnt[basket1[i]]++;cnt[basket2[i]]--;}// 检查可行性for (auto& p : cnt) {if (p.second % 2 != 0) return -1;}vector<int> swap1, swap2;int globalMin = INT_MAX;for (int fruit : basket1) globalMin = min(globalMin, fruit);for (int fruit : basket2) globalMin = min(globalMin, fruit);// 步骤2: 收集需要移动的水果for (auto& p : cnt) {int fruit = p.first;int diff = p.second;if (diff > 0) {swap1.insert(swap1.end(), diff / 2, fruit);} else if (diff < 0) {swap2.insert(swap2.end(), -diff / 2, fruit);}}// 步骤3: 贪心配对sort(swap1.begin(), swap1.end());sort(swap2.rbegin(), swap2.rend());long long cost = 0;for (size_t i = 0; i < swap1.size(); ++i) {cost += min(2LL * globalMin, min((long long)swap1[i], (long long)swap2[i]));}return cost;}
};

Java

import java.util.*;class Solution {public long minCost(int[] basket1, int[] basket2) {Map<Integer, Integer> cnt = new HashMap<>();int n = basket1.length;// 步骤1: 统计差值for (int i = 0; i < n; i++) {cnt.merge(basket1[i], 1, Integer::sum);cnt.merge(basket2[i], -1, Integer::sum);}// 检查可行性for (int diff : cnt.values()) {if (diff % 2 != 0) return -1;}List<Integer> swap1 = new ArrayList<>();List<Integer> swap2 = new ArrayList<>();int globalMin = Integer.MAX_VALUE;for (int fruit : basket1) globalMin = Math.min(globalMin, fruit);for (int fruit : basket2) globalMin = Math.min(globalMin, fruit);// 步骤2: 收集需要移动的水果for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {int fruit = entry.getKey();int diff = entry.getValue();if (diff > 0) {swap1.addAll(Collections.nCopies(diff / 2, fruit));} else if (diff < 0) {swap2.addAll(Collections.nCopies(-diff / 2, fruit));}}// 步骤3: 贪心配对Collections.sort(swap1);swap2.sort(Collections.reverseOrder());long cost = 0;for (int i = 0; i < swap1.size(); i++) {cost += Math.min(2L * globalMin, Math.min(swap1.get(i), swap2.get(i)));}return cost;}
}

Python

from typing import List
from collections import Counterclass Solution:def minCost(self, basket1: List[int], basket2: List[int]) -> int:# 步骤1: 统计差值cnt = Counter(basket1)cnt.subtract(Counter(basket2))# 检查可行性for diff in cnt.values():if diff % 2 != 0:return -1swap1 = []swap2 = []global_min = min(min(basket1), min(basket2))# 步骤2: 收集需要移动的水果for fruit, diff in cnt.items():if diff > 0:swap1.extend([fruit] * (diff // 2))elif diff < 0:swap2.extend([fruit] * (-diff // 2))# 步骤3: 贪心配对swap1.sort()swap2.sort(reverse=True)cost = 0for a, b in zip(swap1, swap2):cost += min(2 * global_min, min(a, b))return cost