LeetCode 870. 优势洗牌
目录
题目描述
题意分析
给两个等长数组
nums1和nums2。可以任意重排nums1，目标是让满足nums1[i] > nums2[i]的下标i尽可能多，返回重排后的nums1。答案不唯一，任何达到最大数量的排列都算对。
有两个约束值得单独拎出来。第一，
nums2不能动，它的顺序就是最终答案里每个位置的「对手」，所以无论中间怎么排序，最后都必须把结果放回nums2原本的位置上——这意味着一旦对nums2排序，就必须同时把原下标带着走。第二，比较是严格大于，相等不算优势，这一点会直接决定判断里写>还是>=。
「任意重排一方去匹配另一方，最大化胜场」是一个信号很强的形状：所有元素都可以自由指派，唯一的限制是每个元素只能用一次，本质是一个二分图最大匹配问题；但由于胜负关系只由数值大小决定、具有传递性，可以不必真的跑匹配，排序后按大小顺序做局部决策就能取到全局最优。$n$ 可以到 $10^5$，$O(n^2)$ 的两两配对不可行，$O(n \log n)$ 的排序则完全够用。
边界要盯住：
nums2中可能有重复值，排序后相邻元素相等时不能假设对手互不相同；nums1中所有元素都可能小于nums2的最小值，此时一场都赢不了，输出只需保证是nums1的一个排列；数组长度可能为 1。
解法：排序 + 田忌赛马贪心
核心思路
先将
nums1排序，并把nums2变成(值, 原下标)后排序。随后从nums2的最大值开始处理，nums1用左右指针表示尚未使用的最小牌和最大牌：
- 若最大牌能严格战胜当前对手，就用最大牌拿下这一局；
- 若最大牌也赢不了，当前对手必然无法被任何剩余牌战胜，就用最小牌承担这次损失。
正确性可以用交换论证说明。设当前对手
b是剩余对手中的最大值：
- 若
maxA <= b，这局在任何方案中都必输；把最小牌放在这里，只会为后面的较弱对手保留更强的牌。- 若
maxA > b，总存在一个最优方案让maxA对阵b。如果某个最优方案用另一张牌x战胜b，而maxA对阵较弱的c，交换两张牌后，maxA > b且x > b >= c，胜场不变；如果该方案原本放弃了b，交换后至多失去maxA在别处的一胜，同时赢下b，总胜场也不会减少。因此每轮贪心选择都能嵌入某个最优方案。循环不变量是：已处理的最强若干对手均按上述规则完成匹配，并且仍存在一个全局最优方案与这些选择一致。
nums2不能真的重排，所以排序时必须保留原下标，最终将选中的牌写回ans[原下标]。
解题步骤
- 升序排序
nums1。- 将
nums2[i]与原下标i绑定，并按数值升序排序。- 用
left、right指向nums1尚未使用区间的两端，从后向前遍历排序后的对手。- 若
nums1[right] > opponent，将最大牌写入对手的原位置并令right--；否则写入最小牌并令left++。- 遍历结束后返回答案数组。
例如
nums1 = [12, 24, 8, 32]、nums2 = [13, 25, 32, 11]。排序后己方为[8, 12, 24, 32]。面对32时最大牌无法取胜，用8放弃；随后依次用32、24、12战胜25、13、11，按原下标写回得到[24, 32, 8, 12]，共赢 3 局。
代码实现
import java.util.Arrays;
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)$。两次排序占主导，双指针分配为 $O(n)$。
- 空间复杂度：$O(n)$。需要保存
nums2的值与原下标，并创建答案数组。
关键点总结
- 对手从强到弱处理：能赢就用最大牌，必输就用最小牌止损。
- “最大牌也赢不了”是当前局必输的充分必要条件，也是贪心成立的关键。
- 交换论证要说明每轮选择都能出现在某个最优方案中，而不只是凭直觉说“田忌赛马”。
- 排序
nums2时必须携带原下标；胜负条件是严格>。
易错点总结
- 排序
nums2却丢失原下标：得到的是对排序后数组的匹配，无法还原题目要求的位置。- 用
>=判断胜利：相等不算优势，必须使用严格大于。- 必输时仍消耗最大牌：例如最大牌与当前对手相等时，这张牌虽然赢不了当前局，却可能战胜后面的较小值。
- 赢了移动
left，输了移动right：会重复使用同一张牌，结果甚至不再是nums1的排列。- 从弱到强时仍套用“最大牌能赢就出最大牌”：会让强牌过早赢弱牌；本实现的决策规则与遍历方向必须成套使用。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 455. 分发饼干 | 简单 | 同为双序列贪心配对，但只需统计数量、无需还原位置，双指针同向推进 |
| 881. 救生艇 | 中等 | 排序后从两端配对，判据是两数之和是否超载，目标是最小化组数 |
| 1029. 两地调度 | 中等 | 按两种选择的差值排序后取前一半，体现「按代价差而非绝对值」排序的贪心 |
| 406. 根据身高重建队列 | 中等 | 同样要在排序后还原位置，但用的是按序插入而非双指针分配 |
| 502. IPO | 困难 | 排序划定可选集合后用大根堆动态取最优，贪心资源是随时间解锁的 |
| 630. 课程表 III | 困难 | 按截止时间排序后配合堆做「后悔」替换，比本题的一次性分配多了反悔机制 |
| 135. 分发糖果 | 困难 | 约束来自左右邻居而非配对，需要正反两趟扫描分别满足两侧条件 |
| 621. 任务调度器 | 中等 | 贪心对象是频次最高的任务，答案由桶结构直接推出而非逐位分配 |