题目

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

选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
交换的成本是 min(basket1i,basket2j) 。

根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -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^5
1 <= basket1i,basket2i <= 10^9

解题思路

核心思想

最终状态与可行性：如果两个果篮最终能够相等，那么它们合并后的总水果集合，必须能被完美地平分成两个完全相同的子集。这意味着，在合并后的总集合中，每一种水果的数量都必须是偶数。如果任何一种水果的总数是奇数，则无法平分，这是判断问题是否可解的首要条件。
需要交换的盈余水果：当问题可解时，两个果篮中某些水果的数量会偏离最终的“目标配置”（即总数的一半）。这些“放错了位置”的水果，无论最初在哪个果篮，都构成了需要被移动的**“盈余水果池”**。我们需要执行的交换次数，恰好是这个池中水果总数的一半。
最小化成本的策略：对于每一次交换，都有两种策略可选：为了最小化总成本，我们对每一次交换都选择更优的策略。关键的洞察在于，在 k 次交换中，起决定性作用的是“盈余水果池”里成本最低的那 k 个水果。因为在直接交换中，我们可以用池中最便宜的 k 个水果去和最贵的 k 个水果配对，这样 min(a, b) 的值将由这些最便宜的水果决定。因此，对于这 k 个最便宜的盈余水果中的每一个 f，其对总成本的贡献是 min(f, 2 * min_val)。
- 策略A (直接交换)：将一个盈余水果 a 与另一个盈余水果 b 直接交换，成本为 min(a, b)。
- 策略B (中介交换)：利用全局成本最低的水果 min_val 作为中介，交换两次，总成本为 2 * min_val。

具体思路

步骤 1: 遍历与高效统计统计 不要遍历两个篮子，而是通过一次遍历，同时处理 basket1[i] 和 basket2[i]。我们可以使用一个哈希表 counts：对 basket1 中的水果执行 ++ 操作，对 basket2 中的水果执行 -- 操作。遍历结束后，counts 中每个水果对应的值就是它在两个篮子中的数量差。同时，在此次遍历中，也一并找到了全局的最小值 min_val，可以最大化单次循环的效率。
步骤 2: 构建盈余列表与可行性检查 接着，遍历上一步生成的 counts 差值哈希表。
- 可行性检查：如果任何水果的数量差 diff 是奇数，意味着该水果的总数是奇数，无法平分，直接返回 -1。
- 构建盈余列表：对于一个水果，其数量差的绝对值 abs(diff) 的一半，即 abs(diff / 2)，代表了它需要被移动的次数。解法将所有这些需要被移动的水果（即盈余水果）添加到一个统一的列表 surplus 中。
步骤 3: 高效找出k个最小成本水果 此时，surplus 列表包含了所有放错了位置的水果，其大小为 2k，其中 k 是需要交换的次数。为了找出其中最便宜的 k 个，我们可以选择不适用排序（复杂度 O(k log k)），而是采用效率更高的 nth_element 算法。此算法能以平均线性时间 O(k) 将列表部分排序，使得列表的前 k 个元素恰好是整个列表中最小的 k 个元素，这正是我们所需要的。
步骤 4: 累加计算最终成本 最后，遍历 surplus 列表的前 k 个元素（即成本最低的 k 个盈余水果）。对于其中的每一个水果 f，它都应用了前述的核心贪心策略，将 min((long long)f, 2LL * min_val) 累加到总成本 total_cost 中。完成遍历后，total_cost 即为最终的最小交换成本。

代码

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        // 步骤 1: 一次遍历计算两个 basket 的频率，同时找到全局最小值
        unordered_map<int, int> counts;
        int min_val = INT_MAX;

        for (size_t i = 0; i < basket1.size(); ++i) {
            counts[basket1[i]]++;
            counts[basket2[i]]--;
            min_val = min({min_val, basket1[i], basket2[i]});
        }


        // 步骤 2: 一次遍历处理所有水果类型，检查可行性并构建盈余列表
        vector<int> surplus; // 存放所有需要移动的水果
        for (auto const& [fruit, diff] : counts) {
            // diff 是 fruit 在 basket1 和 basket2 中的数量差
            if (diff % 2 != 0) {
                return -1; // 如果差值为奇数，说明总数为奇数，不可行
            }
            // diff / 2 是 basket1 相对于目标配置的盈余/亏损数量
            // 例如：b1有4个x, b2有2个x。diff=2。目标是各3个。b1盈余1个。diff/2 = 1。
            // 例如：b1有1个x, b2有5个x。diff=-4。目标是各3个。b1亏损2个。diff/2 = -2。
            for (int i = 0; i < abs(diff / 2); ++i) {
                surplus.push_back(fruit);
            }
        }

        // 步骤 3: 使用 nth_element 计算最小成本 (这部分已是最优)
        int swaps_to_make = surplus.size() / 2;
        if (swaps_to_make > 0) {
            nth_element(surplus.begin(), surplus.begin() + swaps_to_make, surplus.end());
        }

        long long total_cost = 0;
        for (int i = 0; i < swaps_to_make; ++i) {
            long long direct_cost = surplus[i];
            long long bridge_cost = 2LL * min_val;
            total_cost += min(direct_cost, bridge_cost);
        }

        return total_cost;
    }
};

复杂度分析

时间复杂度: O(N)

该算法的平均时间复杂度为线性时间，即 O(N)。

频率统计与差值计算 (步骤 1):
- 遍历两个篮子总共 2N 个元素。
- 对unordered_map的操作（插入和访问）平均时间复杂度为 O(1)。
- 因此，此步骤的复杂度为 O(N)。
构建盈余列表 (步骤 2):
- 遍历 counts 哈希表，其大小最多为 2N。
- 将所有盈余水果放入 surplus 列表，总共放入的元素数量 S 最多为 N。
- 此步骤的复杂度为 O(K + S)，其中 K 是水果种类数，S 是盈余水果数。由于 K 和 S 都不会超过 2N，所以复杂度为 O(N)。
nth_element部分排序 (步骤 3):
- std::nth_element 算法的平均时间复杂度与其操作范围的大小成线性关系。
- 对大小为 S 的 surplus 列表操作，复杂度为 O(S)，即 O(N)。
累加成本 (步骤 4):
- 遍历 surplus 列表的前半部分，循环次数为 S/2。
- 复杂度为 O(S)，即 O(N)。

由于所有步骤都是线性时间复杂度，因此算法总的平均时间复杂度为 O(N)。

空间复杂度: O(N)

算法所需的额外空间主要由哈希表和盈余列表决定，空间复杂度为 O(N)。

哈希表 counts:
- 在最坏情况下，两个篮子中所有的 2N 个水果都不同，哈希表需要存储 2N 个条目。
- 因此，其空间复杂度为 O(N)。
盈余列表 surplus:
- 在最坏情况下（例如一个篮子全是水果A，另一个全是水果B），surplus 列表需要存储 N 个水果。
- 因此，其空间复杂度为 O(N)。

总的额外空间需求为 O(N) + O(N)，所以整体空间复杂度为 O(N)。

2561. 重排水果

beautifulremi

题目