優勢洗牌

• 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