算法编程题-优势洗牌

原题描述

给定两个整数数组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)$
• 空间复杂度：$O(n)$

方法二、红黑树

思路简述

考虑如何优化上一种做法的时间复杂度，遍历的$O(n)$时间复杂度是肯定没有办法优化的，那么删除元素这个操作呢？有没有什么数据结构支持对于数据的增删改查时间复杂度都是$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(nlogn)$
• 空间复杂度：$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(nlogn)$
• 空间复杂度：$O(n)$