Question

2561. 重排水果

English Version

题目描述

你有两个果篮，每个果篮中有 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 <= 105
• 1 <= basket1i,basket2i <= 109

解法

方法一：贪心 + 构造

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

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
}