2561.重排水果

链接：2561.重排水果
难度：Hard
标签：贪心、数组、哈希表
简介：给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

题解 1 - cpp

• 编辑时间：2023-02-05
• 执行用时：140ms
• 内存消耗：83.8MB
• 编程语言：cpp
• 解法介绍：先抵消相同数字, 后最小和最大值进行匹配, 同时考虑两个值通过最小值进行一次交换。

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> m;
        for (auto &v : basket1) m[v]++;
        for (auto &v : basket2) m[v]--;
        vector<int> list;
        int nmin = 0x3f3f3f3f;
        for (auto &item : m) {
            if (item.second % 2  != 0) return -1;
            nmin = min(nmin, item.first);
            for (int i = 0; i < abs(item.second) / 2; i++) list.push_back(item.first);
        }
        sort(list.begin(), list.end());
        long long ans = 0;
        for (int i = 0; i < list.size() / 2; i++) ans += min(list[i], nmin * 2);
        return ans;
    }
};

题解 2 - python

• 编辑时间：2023-02-05
• 执行用时：212ms
• 内存消耗：36.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
  def minCost(self, basket1: List[int], basket2: List[int]) -> int:
      m = Counter()
      for num1, num2 in zip(basket1, basket2):
          m[num1] += 1
          m[num2] -= 1
      nmin = min(m)
      l = []
      for k, v in m.items():
          if v % 2 != 0:
              return -1
          for _ in range(abs(v) // 2):
              l.append(k)
      l.sort()
      ans = 0
      for i in range(len(l) // 2):
          ans += min(l[i], nmin * 2)
      return ans

题解 3 - rust

• 编辑时间：2023-02-05
• 执行用时：32ms
• 内存消耗：4.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_cost(basket1: Vec<i32>, basket2: Vec<i32>) -> i64 {
        use std::collections::HashMap;
        let mut m = HashMap::<i32, i32>::new();
        for num in basket1 {
            let v = m.entry(num).or_insert(0);
            *v += 1;
        }
        for num in basket2 {
            let v = m.entry(num).or_insert(0);
            *v -= 1;
        }
        let mut nmin = i32::MAX;
        let mut list = vec![];
        for (k, v) in m.iter() {
            if *v % 2 != 0 {
                return -1;
            }
            nmin = nmin.min(*k);
            for _ in 0..(*v).abs() / 2 {
                list.push(*k);
            }
        }
        list.sort();
        let mut ans = 0;
        for i in 0..list.len() / 2 {
            ans += list[i].min(nmin * 2) as i64;
        }
        ans
    }
}