2561. 重排水果

题目描述

你有两个果篮，每个果篮中有 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⁹

解法

方法一：贪心 + 构造

我们可以先将两个数组中共有的元素去掉，对于剩下的每个数字，其出现的次数必须为偶数，否则无法构造出相同的数组。不妨记去除共有元素后，两数组分别为 \(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\) 为数组长度。

Python3JavaC++Go

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])

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        int n = basket1.length;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            cnt.merge(basket1[i], 1, Integer::sum);
            cnt.merge(basket2[i], -1, Integer::sum);
        }
        int mi = 1 << 30;
        List<Integer> nums = new ArrayList<>();
        for (var e : cnt.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            if (v % 2 != 0) {
                return -1;
            }
            for (int i = Math.abs(v) / 2; i > 0; --i) {
                nums.add(x);
            }
            mi = Math.min(mi, x);
        }
        Collections.sort(nums);
        int m = nums.size();
        long ans = 0;
        for (int i = 0; i < m / 2; ++i) {
            ans += Math.min(nums.get(i), mi * 2);
        }
        return ans;
    }
}

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        int n = basket1.size();
        unordered_map<int, int> cnt;
        for (int i = 0; i < n; ++i) {
            cnt[basket1[i]]++;
            cnt[basket2[i]]--;
        }
        int mi = 1 << 30;
        vector<int> nums;
        for (auto& [x, v] : cnt) {
            if (v % 2) {
                return -1;
            }
            for (int i = abs(v) / 2; i; --i) {
                nums.push_back(x);
            }
            mi = min(mi, x);
        }
        sort(nums.begin(), nums.end());
        int m = nums.size();
        long long ans = 0;
        for (int i = 0; i < m / 2; ++i) {
            ans += min(nums[i], mi * 2);
        }
        return ans;
    }
};

func minCost(basket1 []int, basket2 []int) (ans int64) {
    cnt := map[int]int{}
    for i, a := range basket1 {
        cnt[a]++
        cnt[basket2[i]]--
    }
    mi := 1 << 30
    nums := []int{}
    for x, v := range cnt {
        if v%2 != 0 {
            return -1
        }
        for i := abs(v) / 2; i > 0; i-- {
            nums = append(nums, x)
        }
        mi = min(mi, x)
    }
    sort.Ints(nums)
    m := len(nums)
    for i := 0; i < m/2; i++ {
        ans += int64(min(nums[i], mi*2))
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

2561. 重排水果

题目描述

解法

方法一：贪心 + 构造

评论