870. 优势洗牌

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

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

示例 1：

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

示例 2：

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

思路：田忌赛马

用垃圾🐎战胜对方的垃圾🐎，如果我方垃圾🐎不能战胜对方垃圾🐎，就让我方去和对面最强的🐎同归于尽。

这里是我可以任意排列我方的马，然后去对战对面的马，每只马只能出场一次。所以思路就是我方弱的如果能打败对方弱的，就打，打不过对方弱的，就去和对方最强的同归于尽。

在代码实现方面，要注意的就是提到的说由于nums2不能排序，所以要创建一个下标数组ids。然后对ids进行排序，让ids[0]对应于nums2最小的下标，让ids[1]对应于nums2第二小的下标,.....以此类推。然后用双指针left和right操作ids，从而知道每个下标所要对应的nums1的元素，也就找到了所要求的nums1的排列。

举个例子：

nums1 = [2,7,11,15], nums2 = [1,10,4,11]

1、我们新建一个ids下标数组。ids = [0,1,2,3] // 里面的值只是初始化和下标一样

2、排序ids。我们需要让ids的下标对应到nums2中的值从小到大的下标。举个例子，ids[0]要对应到nums2中值为1的下标,即ids[0]=0。ids[1]要对应到nums2中值为4的下标，即ids[1]=2.

那么排序后的ids为 [0, 2, 1, 3]，下标是0，1，2，3

3、用双指针left=0和right=len(n)-1，操作ids。我们去遍历nums1中的值(排序过的)，假设v是其值，我们判断v是否大于nums2[ids[left]]，如果v（我方最菜）大于对面最菜，那么我们就可以排列我方这个值放在对面这个值所在的下标中，即ans[ids[left]] = v。如果我方最菜v小于对方最菜，那么我们就将这个值放在对面最强值所在的下标ids[right]，即ans[ids[right]] = v。直到排列完我方所有人员，就完成了所需要的排列组合。

func advantageCount(nums1 []int, nums2 []int) []int {n := len(nums1)ans := make([]int,n)    // 用来存放结果的nums1的排列阵营sort.Ints(nums1)    // 先给nums1排序，从小到大ids := make([]int, n )  // 创建一个下标数组，内容为nums2值从小到大的所对应的下标。即nums[ids[0]] = nums[最菜的]、以此类推for i:=0;i<n;i++{   // 先给数组下标初始化一下，值就是下标，这里是初始化还没排序。ids[i] = i}sort.Slice(ids, func(i,j int) bool {    // 排序数组下标，排序方式是按照ids的值作为下标在nums2中从小到大排序。return nums2[ids[i]] < nums2[ids[j]]    // 排序完成后 nums[ids[i]] = nums[第i菜的下标] })left, right := 0, n-1   // 用双指针，left指向最菜的，right指向最强的for _, v := range nums1 {   // 开始遍历nums1，依次决定我方从最菜到最强应该放在哪个位置才能战胜对方。if v > nums2[ids[left]] {   // 如果我方第一个最菜大于对方第一个最菜，那么我方这个值就可以放在对面所在的下标位置。ans[ids[left]] = vleft++} else {ans[ids[right]] = v     // 如果我方最菜比对方最菜还菜，那么我方最菜的值放到对面最强所在的下标位置。right--}}return ans
}

图中的orderPos就是上面说的下标数组ids。