优势洗牌

• 2019 年 10 月 6 日
• 笔记

优势洗牌

0.导语

本周为刷题第15周，第二篇，本篇将通过两种方法解一道中等难度的题，也就是优势洗牌。下面一起来实践吧！

1.题目

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：

输入：A = [2,7,11,15], B = [1,10,4,11]  输出：[2,11,7,15]  

示例 2：

输入：A = [12,24,8,32], B = [13,25,32,11]  输出：[24,32,8,12]  

提示：

1. 1 <= A.length = B.length <= 10000
2. 0 <= A[i] <= 10^9
3. 0 <= B[i] <= 10^9

2.双端队列1

思路

将A进行排序，对B进行遍历，并获取kay与value，合并建立(value，key)的元组，然后将每个元组放入一个新的list当中，设list为C，并作排序，得到一个排序后的列表，列表中包含多个元组。然后循环遍历A中的元素，将A中的list队头元素与C中的对头元素相比，如果比C中的大，则将C中的对头元组pop出去，否则pop对尾部元素，并A中的元素插入pop出去的index位置(结果list当中的index位置)。

简化版思路就是对A、B两个list进行排序，然后A中的元素比B中的元素大，则将A中的元素与B中的这个元素对应起来，否则就把A中的元素与B中的尾部元素对应起来，然后依此循环即可。

实现

class Solution:      def advantageCount(self, A, B):          res = [-1] * len(A)          A.sort()          C=[]          for k, v in enumerate(B):              C.append((v,k))          C.sort()          for i in range(len(A)):              a = A.pop(0)              b = C[0]              if a > b[0]:                  C.pop(0)              else:                  b = C.pop()              res[b[1]] = a          return res  

分析

时间复杂度：O(NlogN)，空间复杂度：O(N)

3.双端队列2

思路同上，实现如下：

class Solution:      def advantageCount(self, A, B):          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