How do I solve the Rearranging Fruits problem with minimal swap cost?

Start by creating frequency maps for both baskets, then sort and scan both arrays. Minimize swap costs by pairing the smallest elements from both arrays.

What is the time complexity of the Rearranging Fruits problem?

The time complexity is O(n log n), primarily due to the sorting step for both baskets.

Can I optimize the space complexity in the Rearranging Fruits problem?

Yes, you can optimize space by using frequency maps and minimizing unnecessary data structures while still tracking the elements efficiently.

What if the arrays have different sets of elements?

If the arrays contain different elements, it is impossible to make the baskets equal, so you should return -1.

What are common mistakes in solving the Rearranging Fruits problem?

Common mistakes include not handling edge cases where arrays have different elements, failing to minimize swap costs through sorting, and not optimizing space usage.

#2561

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

重排水果

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

数组哈希表贪心排序

题目描述

你有两个果篮，每个果篮中有 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⁵
1 <= basket1_i,basket2_i <= 10⁹

lightbulb

解题思路

方法一：贪心 + 构造

我们可以先将两个数组中共有的元素去掉，对于剩下的每个数字，其出现的次数必须为偶数，否则无法构造出相同的数组。不妨记去除共有元素后，两数组分别为 $a$ 和 $b$ 。

接下来，我们考虑如何进行交换。

如果我们要交换 $a$ 中最小的数，那么我们要在 $b$ 中找到最大的数，与其进行交换；同理，如果我们要交换 $b$ 中最小的数，那么我们要在 $a$ 中找到最大的数，与其进行交换。可以通过排序来实现。

不过，还有另一种交换的方案，我们可以借助一个最小的数 $mi$ 作为过渡元素，将 $a$ 中的数先与 $mi$ 进行交换，再将 $mi$ 与 $b$ 中的数进行交换。这样，交换的成本为 $2 \times mi$ 。

在代码实现上，我们可以直接将数组 $a$ 和 $b$ 合并成数组 $nums$ ，然后对数组 $nums$ 进行排序。接下来枚举前一半的数，计算每次的最小成本，累加到答案中即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        cnt = Counter()
        for a, b in zip(basket1, basket2):
            cnt[a] += 1
            cnt[b] -= 1
        mi = min(cnt)
        nums = []
        for x, v in cnt.items():
            if v % 2:
                return -1
            nums.extend([x] * (abs(v) // 2))
        nums.sort()
        m = len(nums) // 2
        return sum(min(x, mi * 2) for x in nums[:m])

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently track and compare element frequencies between two arrays?
question_mark
Does the candidate recognize the importance of sorting in minimizing swap costs?
question_mark
How well does the candidate optimize for both time and space complexity in a solution?

warning

常见陷阱

外企场景

error
Not handling cases where the two arrays contain different sets of elements, making it impossible to match them.
error
Overlooking the importance of sorting in making swaps efficient, which could lead to a higher swap cost.
error
Failing to optimize the space complexity by using unnecessary data structures for tracking element frequencies.

swap_horiz

进阶变体

外企场景

arrow_right_alt
If the arrays have different sizes, return -1 immediately.
arrow_right_alt
If all elements in the arrays are identical, no swaps are needed.
arrow_right_alt
Consider optimizations for handling very large arrays with a large number of swaps.

help

常见问题

外企场景

继续练习

#2554 从一个范围内选择最多整数 I #2598 执行操作后的最大 MEX #2499 让数组不相等的最小总代价