算法编程题-优势洗牌
摘要：本文将对LeetCode原题优势洗牌进行介绍，从最容易想到的方法开始，循序渐进，一步步优化，对于每一种方法，都给出基于golang语言实现的且通过所有测试用例的完整代码，并且给出相应的复杂度分析。
关键词：LeetCode，面试，排序，贪心，golang
原题描述
给定两个整数数组nums1和nums2，要求给出nums1数组的一个排列，使其相比于nums2的优势最大化，所谓的优势指的就是nums1对应位置大于nums2对应位置的个数。
方法一、排序+二分查找
思路简述
从贪心的角度出发，对于nums2每一个数（相当于是一个对手），nums1这边应该尽可能派出最弱但是又能战胜对方的，因此可以对于nums1排序，基于二分查找从nums1中找最小的大于nums2对应位置的数，如果没有，则取nums1中最小的数应战。但是由于一个数只能用一次，所以要从nums1中删除出战的数字。
代码实现
func advantageCount(nums1 []int, nums2 []int) []int {
sort.Slice(nums1, func(i, j int) bool {
return nums1[i] < nums1[j]
})
n := len(nums1)
res := make([]int, 0, n)
for i := 0; i < n; i++ {
pos := findMinLarger(nums1, nums2[i])
if pos == -1 {
pos = 0
}
res = append(res, nums1[pos])
nums1 = append(nums1[: pos], nums1[pos + 1:]...)
}
return res
}
func findMinLarger(nums []int, target int) int {
n := len(nums)
low := 0
high := n - 1
for low < high {
mid := (low + high) / 2
if nums[mid] > target {
high = mid
} else {
low = mid + 1
}
}
if nums[low] > target {
return low
}
return -1
}
LeetCode运行截图如下：
复杂度分析
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)，因为移除元素这个操作，需要移动数组中的元素，所以每一次选择出战数字的复杂度都是 O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
方法二、红黑树
思路简述
考虑如何优化上一种做法的时间复杂度，遍历的 O ( n ) O(n) O(n)时间复杂度是肯定没有办法优化的，那么删除元素这个操作呢？有没有什么数据结构支持对于数据的增删改查时间复杂度都是 O ( l o g n ) O(logn) O(logn)，且可以方便地进行范围查询，答案其实有很多，比如说跳表，AVL树，红黑树甚至B+树也是可以的。我们这里以红黑树为例来说明这个问题。由于golang标准库中没有红黑树这个数据结构，但是LeetCode针对golang语言提前导入了一个第三方的数据结构包，可以使用其中的红黑树实现。但是这个红黑树在实现这个问题上有很多难受的地方，一个是题目中的数组中是有重复数字的，而这个红黑树数字是不允许重复的，二是这个提供的接口ceiling取的是最小的大于等于某个数的开销，这个由于数组里面是整数，可以通过将目标值加一再去查找解决。具体参考以下的代码实现。
代码实现
import (
rbt "github.com/emirpasic/gods/trees/redblacktree"
)
func advantageCount(nums1 []int, nums2 []int) []int {
rbtree := rbt.NewWithIntComparator()
for _, num := range nums1 {
incrRbtree(rbtree, num)
}
n := len(nums2)
res := make([]int, 0, n)
for i := 0; i < n; i++ {
node, found := rbtree.Ceiling(nums2[i] + 1)
if found {
res = append(res, node.Key.(int))
decrRbtree(rbtree, node.Key.(int))
} else {
res = append(res, -1)
}
}
remainVals := make([]int, 0, n)
keys := rbtree.Keys()
k := 0
for j := range keys {
key := keys[j].(int)
var c int
ret, found := rbtree.Get(key)
if !found {
c = 0
} else {
c = ret.(int)
}
for i := 0; i < c; i++ {
remainVals = append(remainVals, key)
}
}
for i := range res {
if res[i] == -1 {
res[i] = remainVals[k]
k++
}
}
return res
}
func incrRbtree(rbtree *rbt.Tree, val int) {
var count int
ret, found := rbtree.Get(val)
if !found {
count = 0
} else {
count = ret.(int)
}
rbtree.Put(val, count + 1)
}
func decrRbtree(rbtree *rbt.Tree, val int) {
var count int
ret, found := rbtree.Get(val)
if !found {
return
} else {
count = ret.(int)
}
if count == 1 {
rbtree.Remove(val)
return
}
rbtree.Put(val, count - 1)
}
LeetCode运行截图如下：
复杂度分析
- 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度： O ( n ) O(n) O(n)
方法三、贪心
思路简述
换一种贪心策略，按照田忌赛马的思路去想，如果我方当前的最弱马强于对方最弱马，那就用最弱马去对战最弱马，否则去对战对方的最强马。具体过程参考代码实现。
代码实现
func advantageCount(nums1 []int, nums2 []int) []int {
sort.Slice(nums1, func(i, j int) bool {
return nums1[i] < nums1[j]
})
n := len(nums1)
// nums2不能排序
idxs := make([]int, n)
for i := 0; i < n; i++ {
idxs[i] = i
}
sort.Slice(idxs, func(i, j int) bool {
return nums2[idxs[i]] < nums2[idxs[j]]
})
res := make([]int, n)
k := n - 1
j := 0
for _, num := range nums1 {
if num > nums2[idxs[j]] {
res[idxs[j]] = num
j++
} else {
res[idxs[k]] = num
k--
}
}
return res
}
LeetCode运行截图如下：
复杂度分析
- 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度： O ( n ) O(n) O(n)