Code & Func

第15天。emmm，这就半个月了？？

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:

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

Example 2:

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

Note:

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

这道题就是个贪心的思路，确保每个位置上，A[i]的值要么是A中第一个比B[i]大，要么是最小能用的值，这就涉及到了怎么找到第一个比B[i]大的值的问题了，我们可以二叉查找树来实现，这里用STL中的multiset即可：

1
vector<int> advantageCount1(vector<int>& A, vector<int>& B) {
2
    multiset<int> S(A.begin(), A.end());
3
    for(int i = 0;i < B.size(); i++) {
4
        auto it = S.upper_bound(B[i]);
5
        if (it == S.end()) {
6
            it = S.begin();
7
        }
8
        A[i] = *it;
9
        S.erase(it);
10
    }
11
    return A;
12
}

这个方法虽然可以AC，但是时间效率不高，所以我们可以用排序的方法来代替二叉查找树，我们按B从大到小的顺序来填A的值，这样如果A中当前能用的最大值比B[i]要大，那么A[i]为A中当前能用的最大值，否则为A中当前能用的最小值。

1
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
2
    vector<int> res(A.size());
3
    vector<pair<int, int>> val2index(A.size());
4

5
    for(int i = 0;i < val2index.size(); i++) val2index[i] = make_pair(B[i], i);
6
    sort(A.begin(), A.end());
7
    sort(val2index.begin(), val2index.end());
8

9
    int first = 0, last = A.size() - 1;
10
    for(int i = A.size() - 1;i >= 0;i--) {
11
        if (val2index[i].first >= A[last]) {
12
            res[val2index[i].second] = A[first++];
13
        } else {
14
            res[val2index[i].second] = A[last--];
15
        }
4 collapsed lines
16
    }
17

18
    return res;
19
}