算法设计与分析-Week18

发表于

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]

解题思路

本题实际上是田忌赛马问题，要求找出A数组的一种排列方式使得其对于B数组优势最大。
解题思路借助于田忌赛马，用最差的马跟对方最好的马比赛，用略好的马跟对方略差的马比赛，利用这种贪心策略，我遍历B数组的每个元素，对于每个元素在A数组中找到一个略大于它的元素；如果找不到，则用A数组的最小元素。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        multiset<int> s(begin(A), end(A));
        vector<int> res;
        for (int b : B) {
            auto it = s.upper_bound(b);
            if (it == s.end()) it = s.begin();
            res.push_back(*it);
            s.erase(it);
        }
        return res;
    }
};
0%