870. Advantage Shuffle

开源项目
1

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

思路

B中的每一个值都从A中找到比之大的值。

  • 排序A，B
  • B和A都从最大值开始取，如果发现 a > b，进行记录，把a从A中删除
  • 根据B原始位置返回记录的值（a > b），如果记录中无值，则返回A中剩余的值

python


class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        A=sorted(A)
        take = collections.defaultdict(list)
        for b in sorted(B)[::-1]:
            if b < A[-1]: take[b].append(A.pop())
        return [(take[i] or A).pop() for i in B]```