田忌赛马（带索引的数组排序）

870. Advantage Shuffle

Medium

27821FavoriteShare

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]

class Solution {
public:
    static bool Cmp(const pair<int,int>& A,const pair<int,int>& B){
        return A.first < B.first;
    }
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<pair<int,int>> SortedA;
        vector<pair<int,int>> SortedB;
        for(int i = 0;i < A.size();i ++){
            SortedA.push_back(make_pair(A[i],i));
        }
        for(int i = 0;i < B.size();i ++){
            SortedB.push_back(make_pair(B[i],i));
        }
        sort(SortedA.begin(),SortedA.end(),Cmp);
        sort(SortedB.begin(),SortedB.end(),Cmp);
        vector<int> Tmp(A.size(),-1);
        vector<int> vec;
        int IndexA = 0;int IndexB = 0;
        while(IndexA < SortedA.size() && IndexB < SortedB.size()){
            if(SortedA[IndexA].first > SortedB[IndexB].first){
                Tmp[SortedB[IndexB].second] = SortedA[IndexA].first;
                IndexA++;IndexB++;
            }
            else{
                vec.push_back(SortedA[IndexA].first);
                IndexA++;
            }
        }
        for(int i = 0;i < A.size();i ++){
            if(Tmp[i] == -1){
                Tmp[i] = vec.back();
                vec.pop_back();
            }
        }
        return Tmp;
    }
};