重排水果

难度: 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 == bakste2.length
1 <= basket1.length <= 10⁵
1 <= basket1_i,basket2_i <= 10⁹

Submission

运行时间: 120 ms

内存: 37.8 MB

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        b1 = Counter(basket1)
        b2 = Counter(basket2)
        mode = min(min(basket1), min(basket2))
        mode *= 2 
        sub_1 = []
        sub_2 = []
        for k, v in b1.items():
            if b2[k] > 0:
                sub = b2[k] if b2[k] < v else v
                b2[k] -= sub
                v -= sub
            if v % 2: return -1
            if v > 0:
                v //= 2
                for i in range(v):
                    sub_1.append(k)
        for k, v in b2.items():
            if v % 2: return -1
            if v > 0:
                v //= 2
                for i in range(v):
                    sub_2.append(k)
        sub_1.sort()
        sub_2.sort()
        mx = len(sub_1)
        l = r = 0
        ans = 0
        while l < mx:
            if sub_1[l] < sub_2[r]:
                ans += min(sub_1[l],mode)
                l += 1
            else:
                mx -= 1
                ans += min(sub_2[r],mode)
                r += 1


        return ans

Explain

该题解的基本思路是先使用Counter统计两个果篮中各水果的数量，然后确定可以直接匹配的水果数量并减去。剩余的水果将被放入sub_1和sub_2列表中，表示需要交换的水果。这些水果会被排序，然后一对一匹配进行最小成本交换。如果在某种水果的个数不是偶数，那么返回-1，因为不能完全通过交换使得两个篮子中水果相等。交换成本取决于两个水果中较小的那个的成本。

时间复杂度: O(n log n)

空间复杂度: O(n)

# 定义一个求最小交换成本的函数
class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        # 统计两个篮子中水果的出现次数
        b1 = Counter(basket1)
        b2 = Counter(basket2)
        # 获取两篮子中最小水果的成本，以便在交换时使用
        mode = min(min(basket1), min(basket2)) * 2
        sub_1 = [] # basket1中需要交换的水果
        sub_2 = [] # basket2中需要交换的水果
        # 处理basket1的水果
        for k, v in b1.items():
            if b2[k] > 0:
                sub = min(b2[k], v)
                b2[k] -= sub
                v -= sub
            if v % 2: return -1 # 如果剩余水果数为奇数，返回-1
            sub_1.extend([k] * (v // 2)) # 添加剩余的需要交换的水果
        # 处理basket2的水果
        for k, v in b2.items():
            if v % 2: return -1 # 如果剩余水果数为奇数，返回-1
            sub_2.extend([k] * (v // 2)) # 添加剩余的需要交换的水果
        sub_1.sort() # 对需要交换的水果排序
        sub_2.sort()
        mx = len(sub_1)
        l = r = 0
        ans = 0
        # 计算最小交换成本
        while l < mx:
            if sub_1[l] < sub_2[r]:
                ans += min(sub_1[l], mode) # 选择较小成本的水果进行交换
                l += 1
            else:
                mx -= 1
                ans += min(sub_2[r], mode)
                r += 1
        return ans

Explore

使用`b2[k] > 0`条件是为了检查basket2中是否存在与basket1相同类型的水果。这个条件帮助算法确定可以直接匹配并减少交换需求的水果数量。通过减去最小共有数量，我们更新了两个篮子中各自这种水果的剩余数量，从而确定了哪些水果是过剩的，需要参与交换。这一步是优化交换策略的关键，因为它直接减少了需要进行计算和处理的交换次数。

如果任何一种水果在一个篮子中剩余的数量是奇数，那么无法通过偶数次的交换（每次交换涉及两个相同的水果）使两个篮子达到相同的水果数量。因为每次交换都需要从一个篮子向另一个篮子移动相同数量的水果，若初始数量是奇数，则必然会导致至少一个篮子中该水果数量仍为奇数，无法通过完全的交换达到平衡。因此，若发现任何奇数数量的水果，就直接返回-1，表示无法通过交换达到目标。

将sub_1和sub_2列表排序是为了使交换过程更高效和成本更低。通过排序，可以确保我们总是优先考虑成本最低的水果进行交换，或者在必要时使用成本模式进行交换，从而达到最小化总成本的目的。排序后的列表使得在进行一对一匹配时，可以简单地从列表头部开始匹配，确保每次交换都是成本最优的。

这处逻辑是为了确保在进行水果交换时，总是选择较小的成本来执行交换。通过比较sub_1和sub_2中当前位置的水果成本，选择成本较低的水果进行交换，可以有效减少总交换成本。如果sub_1中的水果成本小于sub_2，就使用sub_1的水果进行交换，反之亦然。这种方法可以确保在满足交换需求的同时，尽可能地减少交换的总成本。