870. Advantage Shuffle

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example 1:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

Note:

  1. 1 <= A.length = B.length <= 10000
  2. 0 <= A[i] <= 10^9
  3. 0 <= B[i] <= 10^9

这道题给了我们两个数组A和B,让对A进行重排序,使得每个对应对位置上A中的数字尽可能的大于B。这不就是大名鼎鼎的田忌赛马么,但想出高招并不是田忌,而是孙膑,就是孙子兵法的作者,但这 credit 好像都给了田忌,让人误以为是田忌的智慧,不禁想起了高富帅重金买科研成果的冠名权的故事。孙子原话是,“今以君之下驷与彼上驷,取君上驷与彼中驷,取君中驷与彼下驷”。就是自己的下马跟人上马比,稳输不用管,上马跟其中马跑,稳赢,中马跟其下马跑,还是稳赢。那我还全马跟其半马跑,能赢否?不过说的,今天博主所在的城市还真有马拉松比赛,而且博主还报了半马,但是由于身不由己的原因无法去跑,实在是可惜,没事,来日方长,总是有机会的。扯了这么久的犊子,赶紧拉回来做题吧。其实这道题的思路还真是田忌赛马的智慧一样,既然要想办法大过B中的数,那么对于B中的每个数(可以看作每匹马),先在A中找刚好大于该数的数字(这就是为啥中马跟其下马比,而不是上马跟其下马比),用太大的数字就浪费了,而如果A中没有比之大的数字,就用A中最小的数字(用下马跟其上马比,不过略有不同的是此时我们没有上马)。就用这种贪婪算法的思路就可以成功解题了,为了方便起见,就是用一个 MultiSet 来做,相当于一个允许重复的 TreeSet,既允许重复又自带排序功能,岂不美哉!那么遍历B中每个数字,在A进行二分搜索第一个大于的数字,这里使用了 STL 自带的 upper_bound 来做,当然想自己写二分也没问题。然后看,若不存在,则将A中最小的数字加到结果 res 中,否则就将第一个大于的数字加入结果 res 中,参见代码如下:
解法一:

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> res;
        multiset<int> st(A.begin(), A.end());
        for (int i = 0; i < B.size(); ++i) {
            auto it = (*st.rbegin() <= B[i]) ? st.begin() : st.upper_bound(B[i]);
            res.push_back(*it);
            st.erase(it);
        }
        return res;
    }
};

当两个数组都是有序的时候,我们就能快速的直到各自的最大值与最小值,问题就变得容易很多了。比如可以先从B的最大值开始,这是就看A的最大值能否大过B,能的话,就移动到对应位置,不能的话就用最小值,然后再看B的次大值,这样双指针就可以解决问题。所以可以先给A按从小到大的顺序,对于B的话,不能直接排序,因为这样的话原来的顺序就完全丢失了,所以将B中每个数字和其原始坐标位置组成一个 pair 对儿,加入到一个最大堆中,这样B中的最大值就会最先被取出来,再进行上述的操作,这时候就可以发现保存的原始坐标就发挥用处了,根据其坐标就可以直接更新结果 res 中对应的位置了,参见代码如下:
解法二:

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        int n = A.size(), left = 0, right = n - 1;
        vector<int> res(n);
        sort(A.begin(), A.end());
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < n; ++i) q.push({B[i], i});
        while (!q.empty()) {
            int val = q.top().first, idx = q.top().second; q.pop();
            if (A[right] > val) res[idx] = A[right--];
            else res[idx] = A[left++];
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/870

参考资料:

https://leetcode.com/problems/advantage-shuffle/

https://leetcode.com/problems/advantage-shuffle/discuss/149831/C%2B%2B-6-lines-greedy-O(n-log-n)

https://leetcode.com/problems/advantage-shuffle/discuss/149822/JAVA-Greedy-6-lines-with-Explanation

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation