題目
給定兩個大小相等的陣列 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 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
解題思路分析1、貪心；時間複雜度O(nlog(n))，空間複雜度O(n)
func advantageCount(A []int, B []int) []int { res := make([]int, len(A)) sort.Ints(A) arr := make([][2]int, 0) for i := 0; i < len(B); i++ { arr = append(arr, [2]int{i, B[i]}) } sort.Slice(arr, func(i, j int) bool { return arr[i][1] < arr[j][1] }) left, right := 0, len(A)-1 for i := 0; i < len(A); i++ { if A[i] > arr[left][1] { // 滿足條件放前面 index := arr[left][0] left++ res[index] = A[i] } else { // 不滿足條件放後面 index := arr[right][0] right-- res[index] = A[i] } } return res}Medium題目，本質上是比較經典的田忌賽馬題目，採用貪心策略
最新評論