leetcode 870. Advantage Shuffle

佚名 6年前 (2019-05-10) 随笔 1303人围观抢沙发百度已收录

870. Advantage Shuffle

思路：A数组的最大值大于B的最大值，就拿这个A跟B比较；如果不大于，就拿最小值跟B比较

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

A可以改变顺序，但B的顺序不能改变，只能通过容器来获得由大到小的顺序，并且必须存储相应的index，因为最终需要将选择的A的数值存入与这个B相对应的index下

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> result(A.size());
        sort(A.begin(),A.end());
        priority_queue<pair<int,int>> q;
        for(int i = 0;i < B.size();i++)
            q.push({B[i],i});
        int left = 0,right = A.size() - 1;
        while(left <= right){
            int num = q.top().first;
            int index = q.top().second;
            q.pop();
            if(A[right] > num){
                result[index] = A[right];
                right--;
            }
            else{
                result[index] = A[left];
                left++;
            }
        }
        return result;
    }
};