Formatted question description: https://leetcode.ca/all/870.html
870. Advantage Shuffle (Medium)
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]
Note:
1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
Solution 1.
// OJ: https://leetcode.com/problems/advantage-shuffle/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
sort(A.begin(), A.end());
vector<int> copy(B.begin(), B.end());
sort(B.begin(), B.end());
unordered_map<int, queue<int>> m;
queue<int> leftover;
int i = 0;
for (int a : A) {
if (a > B[i]) m[B[i++]].push(a);
else leftover.push(a);
}
vector<int> ans;
for (int b : copy) {
if (m[b].size()) {
ans.push_back(m[b].front());
m[b].pop();
} else {
ans.push_back(leftover.front());
leftover.pop();
}
}
return ans;
}
};
Java
class Solution {
public int[] advantageCount(int[] A, int[] B) {
int length = A.length;
int[][] arrayA2D = new int[length][2];
int[][] arrayB2D = new int[length][2];
for (int i = 0; i < length; i++) {
arrayB2D[i][0] = B[i];
arrayB2D[i][1] = i;
}
Arrays.sort(arrayB2D, new Comparator<int[]>() {
public int compare(int[] array1, int[] array2) {
return array1[0] - array2[0];
}
});
for (int i = 0; i < length; i++)
arrayA2D[i][1] = arrayB2D[i][1];
Arrays.sort(A);
int index = 0;
for (int i = 0; i < length; i++) {
int num = A[i];
if (num > arrayB2D[index][0]) {
arrayA2D[index][0] = num;
index++;
A[i] = -1;
}
}
for (int i = 0; i < length; i++) {
int num = A[i];
if (num >= 0) {
arrayA2D[index][0] = num;
index++;
}
}
Arrays.sort(arrayA2D, new Comparator<int[]>() {
public int compare(int[] array1, int[] array2) {
return array1[1] - array2[1];
}
});
int[] permutation = new int[length];
for (int i = 0; i < length; i++)
permutation[i] = arrayA2D[i][0];
return permutation;
}
}