LeetCode 870. 优势洗牌
题目描述
题意分析
重新排列
nums1，使满足nums1[i] > nums2[i]的位置数量尽可能多。每个位置只记赢或不赢，不比较赢了多少；相等也不算赢。只要获胜位置数最多，返回任意一种排列即可。可以改变匹配的处理顺序，但答案最终必须对应
nums2的原位置。因此给nums2的每个值绑定原下标后再排序；重复值仍是不同位置，各自分配一个数。代码会原地排序nums1，nums2本身不变。
解法：排序 + 田忌赛马贪心
核心思路
[!blue]
将己方
nums1升序排列，用left、right指向尚未使用的最小值和最大值；对手也按值排序，但从大到小处理。设当前最大对手值为 $b$，己方最大剩余值为 $R$、最小剩余值为 $L$。若 $R\le b$，任何剩余值都无法赢当前局，就用 $L$ 承担这次失败，把更大的值留给较弱对手。这个选择不会降低最优胜场：若某个最优方案用 $x$ 对付 $b$，而把 $L$ 放在另一局，交换二者后当前局仍然输，另一局得到的 $x\ge L$，原来能赢就仍然能赢。
若 $R>b$，就用 $R$ 赢当前局。考虑一个最优方案，其中 $x$ 对付 $b$，而 $R$ 对付另一个不大于 $b$ 的对手 $c$。若 $x>b$，交换后 $R$ 能赢 $b$，$x$ 也能赢 $c$，两场胜利都保留；若 $x\le b$，原先这两局只有 $R$ 对 $c$ 的一胜，交换后至少保住 $R$ 对 $b$ 的一胜。因此总胜场不会减少。
两种情况都说明，可以把某个最优方案调整为当前贪心选择。固定这一局后，对剩余数组重复同样的论证，便得到整体最优的分配。
解题步骤
- 升序排序
nums1；建立(nums2[i], i)数对，并按对手值升序排序。- 令
left = 0、right = n-1，区间[left,right]表示还未分配的己方元素。- 从最大的对手向前遍历。如果
nums1[right]严格大于当前对手，就选择右端并令right--；否则选择左端并令left++。- 将选中的值写入当前对手的原下标位置，而不是排序后的位置。
每轮恰好分配一个己方元素和一个对手位置，已消耗的元素都位于区间之外。处理完
n局后，所有元素恰好使用一次，答案仍是nums1的一个排列。
代码实现
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
int n = nums1.length;
// 把对手值与原下标绑定，排序后仍能恢复对应位置
int[][] pairs = new int[n][2];
for (int i = 0; i < n; i++) {
pairs[i][0] = nums2[i];
pairs[i][1] = i;
}
Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));
int[] ans = new int[n];
int left = 0;
int right = n - 1;
for (int i = n - 1; i >= 0; i--) {
// 分配结果写回对手原位置，不能返回排序后的对应关系
int idx = pairs[i][1];
// 能赢就用最大值赢当前最强对手，否则用最小值牺牲。
if (nums1[right] > pairs[i][0]) {
ans[idx] = nums1[right];
right--;
} else {
ans[idx] = nums1[left];
left++;
}
}
return ans;
}
}
import "sort"
type NumPair struct {
value int
idx int
}
func advantageCount(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
// 把对手值与原下标绑定，排序后仍能恢复对应位置
pairs := make([]NumPair, len(nums2))
for i, num := range nums2 {
pairs[i] = NumPair{value: num, idx: i}
}
sort.Slice(pairs, func(i int, j int) bool {
return pairs[i].value < pairs[j].value
})
ans := make([]int, len(nums1))
left := 0
right := len(nums1) - 1
for i := len(pairs) - 1; i >= 0; i-- {
// 分配结果写回对手原位置，不能返回排序后的对应关系
idx := pairs[i].idx
// 能赢就用最大值赢当前最强对手，否则用最小值牺牲。
if nums1[right] > pairs[i].value {
ans[idx] = nums1[right]
right--
} else {
ans[idx] = nums1[left]
left++
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n\log n)$，两个数组的排序主导；排序后的分配只遍历 $n$ 次。
- 空间复杂度：$O(n)$，保存对手的值和原下标；答案另占 $O(n)$。即使不计返回结果，辅助空间仍为 $O(n)$。
关键点总结
[!green]
- 从最强对手开始，最大值都不能赢时才能确认当前局必输，进而牺牲最小值。
- 能赢时消耗最大值、必输时消耗最小值，两种选择都有交换论证保证不损失最优胜场。
- 排序用于决定分配次序，原下标用于恢复答案位置，两者不能混淆。
易错点总结
[!yellow]
- 丢掉对手原下标，结果只能对应排序后的对手。
- 必输时仍消耗最大值，浪费它对较弱值的胜场。
- 消耗哪端却移动另一端，会重复使用元素。
- 将比较写成
>=：相等不能贡献优势，应归入无法获胜的分支。- 用值作为唯一键保存对手下标：重复值会覆盖位置，应保存每个元素各自的下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 455. 分发饼干 | 简单 | 同样用尽可能小的资源击败当前最小需求，把大值留给更难匹配的对象。 |
| 881. 救生艇 | 中等 | 同样通过排序后的两端选择证明贪心，但救生艇约束两数和，本题约束逐项严格大于。 |