[Swift]LeetCode870. 优势洗牌 | Advantage Shuffle_app

概述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

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,15]

Example 2:

input: A = [12,24,8,32],B = [13,25,32,11] Output: [24,12]

Note:

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= A.length = B.length <= 10000 0 <= A[i] <= 10^9 0 <= B[i] <= 10^9 Runtime: 552 ms Memory Usage: 20.3 MB

 1 class Solution {     2     func advantageCount(_ A: [Int],_ B: [Int]) -> [Int] { 3         var A = A 4         A.sort() 5         var n:Int = A.count 6         var res:[Int] = [Int](repeating:0,count:n) 7         var pq:[[Int]] = [[Int]]() 8         for i in 0..<n 9         {10             pq.append([B[i],i])            11         }12         pq.sort(){$0[0] < $1[0]}13         var lo:Int = 014         var hi:Int = n - 115         while(!pq.isEmpty)16         {17             var cur:[Int] = pq.removeLast()18             var IDx:Int = cur[1]19             var val:Int = cur[0]20             if A[hi] > val21             {22                 res[IDx] = A[hi]23                 hi -= 124             }25             else26             {27                 res[IDx] = A[lo]28                 lo += 129             }30         }31         return res32     }33 }

616ms

 1 class Solution { 2     func advantageCount(_ A: [Int],_ B: [Int]) -> [Int] { 3         var leftArr = [Int]() 4         var ans = [Int](repeating: Int.min,count: A.count) 5         var tupleArrB = [(Int,Int)]() 6         for i in 0..<B.count { 7             tupleArrB.append((i,B[i])) 8         } 9         tupleArrB.sort { $0.1 < $1.1}10         var sorteA = A.sorted()11         var aIndex = 012         for (bi,v) in tupleArrB {13             if aIndex >= sorteA.count { break }14             while aIndex < sorteA.count {15                 let a = sorteA[aIndex]16                 aIndex += 117                 if a > v { ans[bi] = a; break}18                 leftArr.append(a)19             }20         }21 22         for i in 0..<ans.count {23             if ans[i] == Int.min {24                 ans[i] = leftArr.removeFirst()25             }26         }27         return ans28     }29 }

624ms

 1 class Solution { 2     func advantageCount(_ A: [Int],_ B: [Int]) -> [Int] { 3         var res = Array(repeating: 0,count: A.count) 4  5         var A = A.sorted() 6         var i = 0,e = A.count - 1 7         for (IDx,n) in B.enumerated().sorted(by: { $0.1 >= $1.1 }) { 8             if A[e] > n { 9                 res[IDx] = A[e]10                 e -= 111             } else {12                 res[IDx] = A[i]13                 i += 114             }15         }16         return res17     }18 }

628ms

 1 class Solution { 2     func advantageCount(_ A: [Int],_ B: [Int]) -> [Int] { 3         var sorted = A.sorted(by: >) 4         var sortedB = B.enumerated().sorted { 5             $0.1 > $1.1 6         } 7         var i = 0 8         var j = sorted.count - 1 9         var result = [Int](repeating: 0,count: sorted.count)10         for b in sortedB {11             if sorted[i] > b.1 {12                 result[b.0] = sorted[i]13                 i += 114             } else {15                 result[b.0] = sorted[j]16                 j -= 117             }18         }19         return result20     }21 }

772ms

 1 class Solution { 2     func advantageCount(_ A: [Int],_ B: [Int]) -> [Int] { 3         var sortedA = A.sorted(by: <) 4         let sortedB = B.enumerated().map { ($0,$1) }.sorted { $0.1 < $1.1 } 5          6         var hash = [Int:Int]() 7         sortedB.forEach { (index,b) in 8             let IDx = sortedA.index(where: { $0 > b }) ?? 0 9             hash[index] = sortedA.remove(at: IDx)10         }11         12         return (0 ..< B.count).map { hash[$0]! }13     }14 }

976ms

 1 class Solution { 2     func advantageCount(_ A: [Int],_ B: [Int]) -> [Int] { 3         let sortedA = A.sorted() 4         let sortedB = B.sorted() 5          6         var i = 0 7         var results = [Int]() 8         var wastes = [Int]() 9         10         for b in sortedB {11             while i < sortedA.count && sortedA[i] <= b {12                 wastes.append(sortedA[i])13                 i += 114             }15             16             if i == sortedA.count {17                 results += wastes18                 break19             } else {20                 results.append(sortedA[i])21                 i += 122             }23         }24         25         var map = [Int: [Int]]()26         27         for i in 0..<sortedB.count {28             let b = sortedB[i]29             let r = results[i]30             31             if var row = map[b] {32                 row.append(r)33                 map[b] = row34             } else {35                 map[b] = [r]36             }37         }38         39         var realResults = [Int]()40         41         for b in B {42             var row = map[b]!43             realResults.append(row.removeLast())44             map[b] = row45         } 46         return realResults47     }48 }

7176ms

 1 class Solution { 2     func advantageCount(_ A: [Int],_ B: [Int]) -> [Int] { 3         var sortedA = A.sorted(by: <) 4          5         var hash = [Int:Int]() 6          7         return B.map { b in 8             let IDx = sortedA.index(where: { $0 > b }) ?? 0 9             return sortedA.remove(at: IDx)10         }11     }12 }