思路
- 将nums1(自己的马)进行升序排序，得到下等马->上等马的序列
- 贪心策略
- 若某个位置上自己的马比对手的马强，由于已经排过序了，已经是最下等的马了，因此使用这匹马
- 若某个位置上自己的马比对手的马弱，将该下等马放到最后的位置（对手的上等马的位置）
- 由于nums2的顺序固定（已知对手上场顺序），因此使用nums2的元素值对nums2的index进行排序，得到上场顺序（ids）
- 按照上场顺序(ids)依次写入ans数组中
代码
func advantageCount(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
n := len(nums1)
ans := make([]int, n)
ids := make([]int, n)
for i := 0; i < n; i++ {
ids[i] = i
}
sort.Slice(ids, func(i, j int) bool { return nums2[ids[i]] < nums2[ids[j]] })
left, right := 0, n-1
for _, v := range nums1 {
if v > nums2[ids[left]] {
ans[ids[left]] = v
left++
} else {
ans[ids[right]] = v
right--
}
}
return ans
}
总结
灵活运用不对数组进行真正的排序，而是获得排序后的index的顺序这一技巧