870. Advantage Shuffle

Posted on Edited on In

870. Advantage Shuffle

Description

Difficulty: Medium

Related Topics: Array, Two Pointers, Greedy, Sorting

You are given two integer arrays nums1 and nums2 both of the same length. The advantage of nums1 with respect to nums2 is the number of indices i for which nums1[i] > nums2[i].

Return any permutation of nums1 that maximizes its advantage with respect to nums2.

Example 1:

1
2
Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

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

Constraints:

  • 1 <= nums1.length <= 105
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 109

Hints/Notes

  • Use priority queue for nums2, also we need to record the index for each value
  • Need to allocate a new res vector for return, nums1 records sorted array
1
2
3
4
5
6
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        return vector<int>();
    }
}

Solution

Language: C++

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 = [](const pair<int, int> lhs, const pair<int, int> rhs) {
            return lhs.second < rhs.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < nums2.size(); i++) {
            pq.push({i, nums2[i]});
        }
        sort(nums1.begin(), nums1.end());
        int left = 0, right = nums1.size() - 1;
        vector<int> res(nums1.size(), 0);
        while (!pq.empty()) {
            pair<int, int> top = pq.top();
            pq.pop();
            if (top.second >= nums1[right]) {
                res[top.first] = nums1[left++];
            } else {
                res[top.first] = nums1[right--];
            }
        }
        return res;
    }
};