title
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 <= A.length = B.length <= 10000
- 0 <= A[i] <= 10^9
- 0 <= B[i] <= 10^9
solution
查找最大化a[i]>b[i]的i的数量。
a排序后，就可以二分查找，然后贪心法依次比较就是结果了。
class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
sort(A.begin(), A.end());
vector<int> res;
for (auto &it : B) {
int index = upper_bound(A.begin(), A.end(), it) - A.begin();
if (index != A.size()) {
res.push_back(A[index]);
A.erase(A.begin()+index);
}
else {
res.push_back(*A.begin());
A.erase(A.begin());
}
}
for (auto &it : A) {
res.push_back(it);
}
return res;
}
};
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
multiset<int> s(begin(A), end(A));
for (auto i = 0; i < B.size(); ++i) {
auto p = *s.rbegin() <= B[i] ? s.begin() : s.upper_bound(B[i]);
A[i] = *p;
s.erase(p);
}
return A;
}