870. Advantage Shuffle

题目

这道题颇有田忌赛马的意思，尽可能让我们的4匹马赢过对面4匹马。

总的思路来说，尽可能找最大的和对面最大的比，如果胜，这派最大的出战，
如果败，则将最弱的迎战对面对强，即可。

代码(排序)

代码总体来说比较简单。

class Solution:
    def advantageCount(self, A, B):
            A = sorted(A)
            take = collections.defaultdict(list)
            for b in sorted(B)[::-1]:
                if b < A[-1]: take[b].append(A.pop())
            return [(take[b] or A).pop() for b in B]
        '''
        Input: A = [12,24,8,32], B = [13,25,32,11]
        Output: [24,32,8,12]
        # [8,12,24,32]/[11,13,25,32]
        # take[25]=32
        # take [13]=24
        # take[11]=12
        # [24,32,8,12]
    '''

高效代码

class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        # B中有n个数字
        N = len(B)
        # 将B排序
        I = sorted(range(N), key=B.__getitem__)
        res = [0] * N
        leftover = []
        j = 0
        # 对于排序A中的a
        for a in sorted(A): #从小到大比。
        
            if B[I[j]] < a: # optimal placement 如果a>b
                res[I[j]] = a
                j += 1
            else: # a cannot cover remaining in B
                leftover.append(a) #如果a加入到剩余中
        for a in leftover: 
            res[I[j]] = a  #将剩下的扔掉。
            j += 1
        return res