870. 优势洗牌 - 力扣（LeetCode）

思路

  1. 将nums1(自己的马)进行升序排序，得到下等马->上等马的序列
  2. 贪心策略
    • 若某个位置上自己的马比对手的马强，由于已经排过序了，已经是最下等的马了，因此使用这匹马
    • 若某个位置上自己的马比对手的马弱，将该下等马放到最后的位置（对手的上等马的位置）
  3. 由于nums2的顺序固定（已知对手上场顺序），因此使用nums2的元素值对nums2的index进行排序，得到上场顺序（ids）
  4. 按照上场顺序(ids)依次写入ans数组中

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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的顺序这一技巧