##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/870.html

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. 1 <= A.length = B.length <= 10000
2. 0 <= A[i] <= 10^9
3. 0 <= B[i] <= 10^9

## Solution 1.

• 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;
}
}

############

class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
int[][] t = new int[n][2];
for (int i = 0; i < n; ++i) {
t[i] = new int[] {nums2[i], i};
}
Arrays.sort(t, (a, b) -> a[0] - b[0]);
Arrays.sort(nums1);
int[] ans = new int[n];
int i = 0, j = n - 1;
for (int v : nums1) {
if (v <= t[i][0]) {
ans[t[j--][1]] = v;
} else {
ans[t[i++][1]] = v;
}
}
return ans;
}
}

• // 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) {
int N = A.size(), i = 0;
vector<int> ia(N), ib(N), ans(N, -1);
iota(begin(ia), end(ia), 0);
iota(begin(ib), end(ib), 0);
sort(begin(ia), end(ia), [&](int a, int b) { return A[a] > A[b]; });
sort(begin(ib), end(ib), [&](int a, int b) { return B[a] > B[b]; });
for (int j = 0; i < N && j < N; ++i) {
while (j < N && B[ib[j]] >= A[ia[i]]) ++j;
if (j < N) {
ans[ib[j++]] = A[ia[i]];
} else break;
}
for (int j = 0; i < N && j < N; ++i) {
while (j < N && ans[j] != -1) ++j;
if (j < N) {
ans[j++] = A[ia[i]];
}
}
return ans;
}
};

• class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
t = sorted((v, i) for i, v in enumerate(nums2))
n = len(nums2)
ans = [0] * n
i, j = 0, n - 1
for v in nums1:
if v <= t[i][0]:
ans[t[j][1]] = v
j -= 1
else:
ans[t[i][1]] = v
i += 1
return ans

############

class Solution(object):
"""
:type A: List[int]
:type B: List[int]
:rtype: List[int]
"""
res = [-1] * len(A)
A = collections.deque(sorted(A))
B = collections.deque(sorted((b, i) for i, b in enumerate(B)))
for i in range(len(A)):
a = A.popleft()
b = B[0]
if a > b[0]:
B.popleft()
else:
b = B.pop()
res[b[1]] = a
return res

• func advantageCount(nums1 []int, nums2 []int) []int {
n := len(nums1)
t := make([][]int, n)
for i, v := range nums2 {
t[i] = []int{v, i}
}
sort.Slice(t, func(i, j int) bool {
return t[i][0] < t[j][0]
})
sort.Ints(nums1)
ans := make([]int, n)
i, j := 0, n-1
for _, v := range nums1 {
if v <= t[i][0] {
ans[t[j][1]] = v
j--
} else {
ans[t[i][1]] = v
i++
}
}
return ans
}

• function advantageCount(nums1: number[], nums2: number[]): number[] {
const n = nums1.length;
const idx = Array.from({ length: n }, (_, i) => i);
idx.sort((i, j) => nums2[i] - nums2[j]);
nums1.sort((a, b) => a - b);

const ans = new Array(n).fill(0);
let left = 0;
let right = n - 1;
for (let i = 0; i < n; i++) {
if (nums1[i] > nums2[idx[left]]) {
ans[idx[left]] = nums1[i];
left++;
} else {
ans[idx[right]] = nums1[i];
right--;
}
}
return ans;
}


• impl Solution {
pub fn advantage_count(mut nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
let n = nums1.len();
let mut idx = (0..n).collect::<Vec<usize>>();
idx.sort_by(|&i, &j| nums2[i].cmp(&nums2[j]));
nums1.sort();
let mut res = vec![0; n];
let mut left = 0;
let mut right = n - 1;
for &num in nums1.iter() {
if num > nums2[idx[left]] {
res[idx[left]] = num;
left += 1;
} else {
res[idx[right]] = num;
right -= 1;
}
}
res
}
}