侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 28 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-10-09 / 0 评论 / 0 点赞 / 335 阅读 / 820 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

870. 优势洗牌


给定两个大小相等的数组 nums1 和 nums2nums1 相对于 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 中的元素可能会重复,所以可以维护一个可重复的有序集合( TreeMapTreeMapmultisetmultiset) ,然后把 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;
    }
};
0

评论区