田忌赛马背后的算法决策
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 870. Advantage Shuffle | 870. 优势洗牌 | 🟠 |
———–
田忌赛马的故事大家应该都听说过：
田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应着比赛，田忌赢不了齐王。但是田忌遇到了孙膑，孙膑就教他用自己的下等马对齐王的上等马，再用自己的上等马对齐王的中等马，最后用自己的中等马对齐王的下等马，结果三局两胜，田忌赢了。
当然，这段历史也挺有意思的，那个讽齐王纳谏，自恋的不行的邹忌和田忌是同一时期的人，他俩后来就杠上了。不过这是题外话，我们这里就打住。
以前学到田忌赛马课文的时，我就在想，如果不是三匹马比赛，而是一百匹马比赛，孙膑还能不能合理地安排比赛的顺序，赢得齐王呢？
当时没想出什么好的点子，只觉得这里面最核心问题是要尽可能让自己占便宜，让对方吃亏。总结来说就是，打得过就打，打不过就拿自己的垃圾和对方的精锐互换。
不过，我一直没具体把这个思路实现出来，直到最近刷到力扣第 870 题「 优势洗牌」，一眼就发现这是田忌赛马问题的加强版：
给你输入两个长度相等的数组 nums1 和 nums2，请你重新组织 nums1 中元素的位置，使得 nums1 的「优势」最大化。
如果 nums1[i] > nums2[i]，就是说 nums1 在索引 i 上对 nums2[i] 有「优势」。优势最大化也就是说让你重新组织 nums1，尽可能多的让 nums1[i] > nums2[i]。
算法签名如下：
int[] advantageCount(int[] nums1, int[] nums2);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def advantageCount(nums1: List[int], nums2: List[int]) -> List[int]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func advantageCount(nums1 []int, nums2 []int) []int {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var advantageCount = function(nums1, nums2) {
/* code here */
}
比如输入：
nums1 = [12,24,8,32]
nums2 = [13,25,32,11]
你的算法应该返回 [24,32,8,12]，因为这样排列 nums1 的话有三个元素都有「优势」。
这就像田忌赛马的情景，nums1 就是田忌的马，nums2 就是齐王的马，数组中的元素就是马的战斗力，你就是孙膑，展示你真正的技术吧。
仔细想想，这个题的解法还是有点扑朔迷离的。什么时候应该放弃抵抗去送人头，什么时候应该硬刚？这里面应该有一种算法策略来最大化「优势」。
送人头一定是迫不得已而为之的权宜之计，否则隔壁田忌就会以为你是齐王买来的演员。只有田忌的上等马比不过齐王的上等马时，才会用下等马去和齐王的上等马互换。
对于比较复杂的问题，可以尝试从特殊情况考虑。
你想，谁应该去应对齐王最快的马？肯定是田忌最快的那匹马，我们简称一号选手。
如果田忌的一号选手比不过齐王的一号选手，那其他马肯定是白给了，显然这种情况应该用田忌垫底的马去送人头，降低己方损失，保存实力，增加接下来比赛的胜率。
但如果田忌的一号选手能比得过齐王的一号选手，那就和齐王硬刚好了，反正这把田忌可以赢。
你也许说，这种情况下说不定田忌的二号选手也能干得过齐王的一号选手？如果可以的话，让二号选手去对决齐王的一号选手，不是更节约？
就好比，如果考 60 分就能过的话，何必考 90 分？每多考一分就亏一分，刚刚好卡在 60 分是最划算的。
这种节约的策略是没问题的，但是没有必要。这也是本题有趣的地方，需要绕个脑筋急转弯：
我们暂且把田忌的一号选手称为 T1，二号选手称为 T2，齐王的一号选手称为 Q1。
如果 T2 能赢 Q1，你试图保存己方实力，让 T2 去战 Q1，把 T1 留着是为了对付谁？
显然，你担心齐王还有战力大于 T2 的马，可以让 T1 去对付。
但是你仔细想想，现在 T2 已经是可以战胜 Q1 的，Q1 可是齐王的最快的马耶，齐王剩下的那些马里，怎么可能还有比 T2 更强的马？
所以，没必要节约，最后我们得出的策略就是：
将齐王和田忌的马按照战斗力排序，然后按照排名一一对比。如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力。
上述思路的代码逻辑如下：
int n = nums1.length;
sort(nums1); // 田忌的马
sort(nums2); // 齐王的马
// 从最快的马开始比
for (int i = n - 1; i >= 0; i--) {
if (nums1[i] > nums2[i]) {
// 比得过，跟他比
} else {
// 比不过，换个垫底的来送人头
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int n = sizeof(nums1) / sizeof(nums1[0]);
sort(nums1, nums1 + n); // 田忌的马
sort(nums2, nums2 + n); // 齐王的马
// 从最快的马开始比
for (int i = n - 1; i >= 0; i--) {
if (nums1[i] > nums2[i]) {
// 比得过，跟他比
} else {
// 比不过，换个垫底的来送人头
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
n = len(nums1)
nums1.sort() # 田忌的马
nums2.sort() # 齐王的马
# 从最快的马开始比
for i in range(n-1, -1, -1):
if nums1[i] > nums2[i]:
# 比得过，跟他比
pass
else:
# 比不过，换个垫底的来送人头
pass
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
n := len(nums1)
sort.Ints(nums1) // 田忌的马
sort.Ints(nums2) // 齐王的马
// 从最快的马开始比
for i := n - 1; i >= 0; i-- {
if nums1[i] > nums2[i] {
// 比得过，跟他比
} else {
// 比不过，换个垫底的来送人头
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var n = nums1.length;
nums1.sort(); // 田忌的马
nums2.sort(); // 齐王的马
// 从最快的马开始比
for (var i = n - 1; i >= 0; i--) {
if (nums1[i] > nums2[i]) {
// 比得过，跟他比
} else {
// 比不过，换个垫底的来送人头
}
}
根据这个思路，我们需要对两个数组排序，但是 nums2 中元素的顺序不能改变，因为计算结果的顺序依赖 nums2 的顺序，所以不能直接对 nums2 进行排序，而是利用其他数据结构来辅助。
同时，最终的解法还用到前文 双指针技巧汇总 总结的双指针算法模板，用以处理「送人头」的情况：
int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
// 给 nums2 降序排序
PriorityQueue<int[]> maxpq = new PriorityQueue<>(
(int[] pair1, int[] pair2) -> {
return pair2[1] - pair1[1];
}
);
for (int i = 0; i < n; i++) {
maxpq.offer(new int[]{i, nums2[i]});
}
// 给 nums1 升序排序
Arrays.sort(nums1);
// nums1[left] 是最小值，nums1[right] 是最大值
int left = 0, right = n - 1;
int[] res = new int[n];
while (!maxpq.isEmpty()) {
int[] pair = maxpq.poll();
// maxval 是 nums2 中的最大值，i 是对应索引
int i = pair[0], maxval = pair[1];
if (maxval < nums1[right]) {
// 如果 nums1[right] 能胜过 maxval，那就自己上
res[i] = nums1[right];
right--;
} else {
// 否则用最小值混一下，养精蓄锐
res[i] = nums1[left];
left++;
}
}
return res;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
// 给 nums2 降序排序
priority_queue<pair<int, int>> maxpq;
for (int i = 0; i < n; i++) {
maxpq.emplace(i, nums2[i]);
}
// 给 nums1 升序排序
sort(nums1.begin(), nums1.end());
// nums1[left] 是最小值，nums1[right] 是最大值
int left = 0, right = n - 1;
vector<int> res(n);
while (!maxpq.empty()) {
auto [i, maxval] = maxpq.top();
maxpq.pop();
if (maxval < nums1[right]) {
// 如果 nums1[right] 能胜过 maxval，那就自己上
res[i] = nums1[right];
right--;
} else {
// 否则用最小值混一下，养精蓄锐
res[i] = nums1[left];
left++;
}
}
return res;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
import heapq
def advantageCount(nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
# 给 nums2 降序排序
maxpq = [(-val, i) for i, val in enumerate(nums2)]
heapq.heapify(maxpq)
# 给 nums1 升序排序
nums1.sort()
# nums1[left] 是最小值，nums1[right] 是最大值
left, right = 0, n - 1
res = [0] * n
while maxpq:
val, i = heapq.heappop(maxpq)
# maxval 是 nums2 中的最大值，i 是对应索引
maxval = -val
if maxval < nums1[right]:
# 如果 nums1[right] 能胜过 maxval，那就自己上
res[i] = nums1[right]
right -= 1
else:
# 否则用最小值混一下，养精蓄锐
res[i] = nums1[left]
left += 1
return res
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func advantageCount(nums1 []int, nums2 []int) []int {
n := len(nums1)
// 给 nums2 降序排序
maxPq := make(PriorityQueue, 0)
heap.Init(&maxPq)
for i := 0; i < n; i++ {
pair := []int{i, nums2[i]}
heap.Push(&maxPq, pair)
}
// 给 nums1 升序排序
sort.Ints(nums1)
// nums1[left] 是最小值，nums1[right] 是最大值
left, right := 0, n - 1
res := make([]int, n)
for maxPq.Len() > 0 {
pair := heap.Pop(&maxPq).([]int)
// maxval 是 nums2 中的最大值，i 是对应索引
i, maxval := pair[0], pair[1]
if maxval < nums1[right] {
// 如果 nums1[right] 能胜过 maxval，那就自己上
res[i] = nums1[right]
right--
} else {
// 否则用最小值混一下，养精蓄锐
res[i] = nums1[left]
left++
}
}
return res
}
type PriorityQueue [][]int
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i][1] > pq[j][1]
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.([]int))
}
func (pq *PriorityQueue) Pop() interface{} {
n := len(*pq)
item := (*pq)[n-1]
*pq = (*pq)[:n-1]
return item
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var advantageCount = function(nums1, nums2) {
var n = nums1.length;
// 给 nums2 降序排序
var maxpq = new PriorityQueue(function(a, b) {
return b[1] - a[1];
});
for (var i = 0; i < n; i++) {
maxpq.push([i, nums2[i]]);
}
// 给 nums1 升序排序
nums1.sort(function(a, b) {
return a - b;
});
// nums1[left] 是最小值，nums1[right] 是最大值
var left = 0, right = n - 1;
var res = [];
while (maxpq.length > 0) {
var pair = maxpq.pop();
// maxval 是 nums2 中的最大值，i 是对应索引
var i = pair[0], maxval = pair[1];
if (maxval < nums1[right]) {
// 如果 nums1[right] 能胜过 maxval，那就自己上
res[i] = nums1[right];
right--;
} else {
// 否则用最小值混一下，养精蓄锐
res[i] = nums1[left];
left++;
}
}
return res;
};
算法的时间复杂度很好分析，也就是二叉堆和排序的复杂度 O(nlogn)。
至此，这道田忌赛马的题就解决了，其代码实现上用到了双指针技巧，从最快的马开始，比得过就比，比不过就送，这样就能对任意数量的马求取一个最优的比赛策略了。
最后打个广告，我亲自制作了一门 数据结构精品课，以视频课为主，手把手带你实现常用的数据结构及相关算法，旨在帮助算法基础较为薄弱的读者深入理解常用数据结构的底层原理，在算法学习中少走弯路。
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释