Advantage Shuffle

Description

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(javascript)

// Deque
const advantageCount = function (A = [], B = []) {
  A.sort((a, b) => b - a)
  const indexes = B.map((v, index) => index).sort((a, b) => B[b] - B[a])
  const result = []
  for (let i = 0; i < indexes.length; i++) {
    const index = indexes[i]
    // 这里的复杂度其实是 O(n)
    result[index] = A[0] > B[index] ? A.shift() : A.pop()
  }
  return result
}