Victoria Island

be curious, be free

0%

优势洗牌(田忌赛马)

发表于 更新于 分类于 本文字数： 699 阅读时长 ≈ 1 分钟

贪心

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