Hard

题目描述

你有两个水果篮，每个篮子都有 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. 频率统计与可行性检查：首先统计两个篮子中每个数字的出现频率。如果某个数字在两个篮子中的总出现次数是奇数，说明无法平均分配，直接返回-1。

  2. 确定需要交换的数字：对于每个数字，计算其在最终状态下应该在每个篮子中的数量（总数量的一半）。如果某个篮子中该数字过多，需要转移给另一个篮子。

  3. 贪心策略优化交换成本：

    • 直接交换：将篮子1中多余的数字直接与篮子2中多余的数字交换，成本为两者的最小值
    • 中转交换：利用全局最小值作为中转，先将多余数字换成最小值，再用最小值换取需要的数字，成本为 2 * min_val

  4. 排序优化：将需要交换的数字按升序排列，优先交换较小的数字以最小化总成本。

这种方法的关键在于识别何时使用中转交换更优。当直接交换的成本超过中转交换时，选择中转策略。

代码实现

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> count;
        
        // Count frequencies
        for (int x : basket1) count[x]++;
        for (int x : basket2) count[x]--;
        
        // Find minimum element
        int min_val = min(*min_element(basket1.begin(), basket1.end()),
                         *min_element(basket2.begin(), basket2.end()));
        
        vector<int> need_swap;
        
        for (auto& [val, diff] : count) {
            if (diff % 2 != 0) return -1;
            
            // Add elements that need to be swapped
            int swap_count = abs(diff) / 2;
            for (int i = 0; i < swap_count; i++) {
                need_swap.push_back(val);
            }
        }
        
        sort(need_swap.begin(), need_swap.end());
        
        long long cost = 0;
        int n = need_swap.size();
        
        for (int i = 0; i < n / 2; i++) {
            // Choose minimum between direct swap and using min_val as mediator
            cost += min(need_swap[i], 2LL * min_val);
        }
        
        return cost;
    }
};

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        from collections import Counter
        
        count = Counter(basket1)
        for x in basket2:
            count[x] -= 1
        
        min_val = min(min(basket1), min(basket2))
        need_swap = []
        
        for val, diff in count.items():
            if diff % 2 != 0:
                return -1
            
            swap_count = abs(diff) // 2
            need_swap.extend([val] * swap_count)
        
        need_swap.sort()
        n = len(need_swap)
        cost = 0
        
        for i in range(n // 2):
            cost += min(need_swap[i], 2 * min_val)
        
        return cost

public class Solution {
    public long MinCost(int[] basket1, int[] basket2) {
        var count = new Dictionary<int, int>();
        
        foreach (int x in basket1) {
            count[x] = count.GetValueOrDefault(x, 0) + 1;
        }
        foreach (int x in basket2) {
            count[x] = count.GetValueOrDefault(x, 0) - 1;
        }
        
        int minVal = Math.Min(basket1.Min(), basket2.Min());
        var needSwap = new List<int>();
        
        foreach (var kvp in count) {
            if (kvp.Value % 2 != 0) return -1;
            
            int swapCount = Math.Abs(kvp.Value) / 2;
            for (int i = 0; i < swapCount; i++) {
                needSwap.Add(kvp.Key);
            }
        }
        
        needSwap.Sort();
        long cost = 0;
        
        for (int i = 0; i < needSwap.Count / 2; i++) {
            cost += Math.Min(needSwap[i], 2L * minVal);
        }
        
        return cost;
    }
}

var minCost = function(basket1, basket2) {
    const count = new Map();
    
    for (const x of basket1) {
        count.set(x, (count.get(x) || 0) + 1);
    }
    for (const x of basket2) {
        count.set(x, (count.get(x) || 0) - 1);
    }
    
    const minVal = Math.min(Math.min(...basket1), Math.min(...basket2));
    const needSwap = [];
    
    for (const [val, diff] of count) {
        if (diff % 2 !== 0) return -1;
        
        const swapCount = Math.abs(diff) / 2;
        for (let i = 0; i < swapCount; i++) {
            needSwap.push(val);
        }
    }
    
    needSwap.sort((a, b) => a - b);
    let cost = 0;
    
    for (let i = 0; i < Math.floor(needSwap.length / 2); i++) {
        cost += Math.min(needSwap[i], 2 * minVal);
    }
    
    return cost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是数组的长度。时间复杂度主要由排序操作决定，空间复杂度用于存储频率统计和需要交换的元素。

相关题目