870. Advantage Shuffle

發表於 | 分類於

problem

solution

將nums1 排序，將nums2 {nums2[i], i} push 進heap，每次從heap 派出最大，與nums1[r] 比較大小，如果大於等於nums1[r]，打不過，那就派出最爛的nums1[l]，反之派出最強的nums[r]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        auto cmp = [](pair<int,int> & a, pair<int,int>& b){
            return a.first<b.first;
        };
        priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp) > pq(cmp);
        for(int i=0;i<nums2.size();++i) pq.push(make_pair(nums2[i], i) );
        
        sort(nums1.begin(),nums1.end());
        vector<int>ret(nums1.size(), 0);
        int l = 0, r = nums1.size()-1;
        while(!pq.empty()){
            int maxVal = pq.top().first, i = pq.top().second;
            pq.pop();
            if(maxVal >= nums1[r]){
                ret[i] = nums1[l++];
            }
            else{
                ret[i] = nums1[r--];
            }
        }
        return ret;
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(n)