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`

``````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;
}
};
``````

``````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