【哈希表, 有序集合, 优先队列】优势洗牌

题目

870. 优势洗牌

---

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

示例 1：

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

示例 2：

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

提示：

• 1 <= nums1.length <= 10^5
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 10^9

解题

方法一：哈希表

思路

本题其实就是田忌赛马，与：【贪心, 二分查找, 双指针】运动员和训练师的最大匹配数【力扣第 87 场双周赛】 有一定的相似性。

具体来说：遍历 nums2 ，对于每个元素应该选择 nums1 中比其大的最小数，如果不存在这样的数就选择 nums1 中最小的数。
由于 nums1 中的元素可能会重复，所以可以维护一个可重复的有序集合( $TreeMap$ 、$multiset$) ，然后把 nums1 中的所有元素都加入其中以供查找和选择。

代码

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums1) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int i = 0; i < n; ++i) {
            Integer target = map.higherKey(nums2[i]);
            if (target == null) target = map.firstKey();
            nums1[i] = target;
            map.put(target, map.get(target) - 1);
            map.remove(target, 0);
        }
        return nums1;
    }
}

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        multiset<int> st(nums1.begin(), nums1.end());
        for (int i = 0; i < n; ++i) {
            auto it = st.upper_bound(nums2[i]);
            if (it == st.end()) it = st.begin();
            nums1[i] = *it;
            st.erase(it);
        }
        return nums1;
    }
};

方法二：优先队列(大根堆)

思路

思路与方法一一样，都是要把两个数组都排序，然后从大到小依次对比，如果 nums1[i] > nums2[i] 就保留位置不变，否则就把 nums1[i] 换为 nums1 中最小的元素。

但是由于要通过 nums2 来确定 nums1，所以 nums2 中元素顺序是不能改变的，所以不能直接对 nums2 进行排序，这里选择维护一个存储着 nums2 中每个元素及其索引的大根堆，且该堆根据元素大小进行排序。

代码

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < n; ++i) pq.offer(new int[]{i, nums2[i]});
        Arrays.sort(nums1);
        int min = 0, max = n - 1;
        int[] ans = new int[n];
        while (!pq.isEmpty()) {
            int[] tmp = pq.poll();
            int i = tmp[0], num = tmp[1];
            ans[i] = nums1[max] > num ? nums1[max--] : nums1[min++];
        }
        return ans;
    }
}

auto cmp = [](pair<int, int>& a, pair<int, int>& b) -> bool { return a.second < b.second; };

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < n; ++i) pq.push({i, nums2[i]});
        sort(nums1.begin(), nums1.end());
        vector<int> ans(n);
        int mn = 0, mx = n - 1;
        while (!pq.empty()) {
            auto pr = pq.top();
            int i = pr.first, num = pr.second;
            pq.pop();
            ans[i] = nums1[mx] <= num ? nums1[mn++] : nums1[mx--];
        }
        return ans;
    }
};