算法大师——孙膑

系统管理员 2022-09-10 07:21 178阅读 0赞

**读完本文，可以去力扣解决如下题目：**

##  ##

**870. 优势洗牌（****Medium****）**

![bfec15c1027652203f6d7898360d26ae.png][]

田忌赛马的故事大家应该都听说过：

田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应着比赛，田忌赢不了齐王。但是田忌遇到了孙膑，孙膑就教他用自己的下等马对齐王的上等马，再用自己的上等马对齐王的中等马，最后用自己的中等马对齐王的下等马，结果三局两胜，田忌赢了。

当然，这段历史也挺有意思的，那个讽齐王纳谏，自恋的不行的邹忌和田忌是同一时期的人，他俩后来就杠上了。不过这是题外话，我们这里就打住。

以前学到田忌赛马课文的时，我就在想，如果不是三匹马比赛，而是一百匹马比赛，孙膑还能不能合理地安排比赛的顺序，赢得齐王呢？

当时没想出什么好的点子，只觉得这里面最核心问题是要尽可能让自己占便宜，让对方吃亏。总结来说就是，**打得过就打，打不过就拿自己的垃圾和对方的精锐互换**。

不过，我一直没具体把这个思路实现出来，直到最近刷到力扣第 870 题「优势洗牌」，一眼就发现这是田忌赛马问题的加强版：

给你输入两个**长度相等**的数组`nums1`和`nums2`，请你重新组织`nums1`中元素的位置，使得`nums1`的「优势」最大化。

如果`nums1[i] > nums2[i]`，就是说`nums1`在索引`i`上对`nums2[i]`有「优势」。优势最大化也就是说让你重新组织`nums1`，**尽可能多的让`nums[i] > nums2[i]`**。

算法签名如下：

int[] advantageCount(int[] nums1, int[] nums2);

比如输入：

`nums1 = [12,24,8,32]`  
`nums2 = [13,25,32,11]`

你的算法应该返回`[24,32,8,12]`，因为这样排列`nums1`的话有三个元素都有「优势」。

**这就像田忌赛马的情景，`nums1`就是田忌的马，`nums2`就是齐王的马，数组中的元素就是马的战斗力，你就是孙膑，展示你真正的技术吧**。

仔细想想，这个题的解法还是有点扑朔迷离的。什么时候应该放弃抵抗去送人头，什么时候应该硬刚？这里面应该有一种算法策略来最大化「优势」。

送人头一定是迫不得已而为之的权宜之计，否则隔壁田忌就要开语音骂你菜了。只有田忌的上等马比不过齐王的上等马时，所以才会用下等马去和齐王的上等马互换。

对于比较复杂的问题，可以尝试从特殊情况考虑。

你想，谁应该去应对齐王最快的马？肯定是田忌最快的那匹马，我们简称一号选手。

**如果田忌的一号选手比不过齐王的一号选手**，那其他马肯定是白给了，显然这种情况肯定应该用田忌垫底的马去送人头，降低己方损失，保存实力，增加接下来比赛的胜率。

**但如果田忌的一号选手能比得过齐王的一号选手**，那就和齐王硬刚好了，反正这把田忌可以赢。

你也许说，这种情况下说不定田忌的二号选手也能干得过齐王的一号选手？如果可以的话，让二号选手去对决齐王的一号选手，不是更节约？

就好比，如果考 60 分就能过的话，何必考 61 分？每多考一分就亏一分，刚刚好卡在 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 {
            // 比不过，换个垫底的来送人头
        }
    }

根据这个思路，我们需要对两个数组排序，但是`nums2`中元素的顺序不能改变，因为计算结果的顺序依赖`nums2`的顺序，所以不能直接对`nums2`进行排序，而是利用其他数据结构来辅助。

同时，最终的解法还用到前文 [双指针技巧汇总][Link 1] 总结的双指针算法模板，用以处理「送人头」的情况：

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;
    }

算法的时间复杂度很好分析，也就是二叉堆和排序的复杂度`O(nlogn)`。

至此，这道田忌赛马的题就解决了，其代码实现上用到了双指针技巧，从最快的马开始，比得过就比，比不过就送，这样就能对任意数量的马求取一个最优的比赛策略了。

好了，田忌赛马的问题没什么可说的了，有兴趣不妨了解下田忌和邹忌的故事，值得思考。

＿＿＿＿＿＿＿＿＿＿＿＿＿

[bfec15c1027652203f6d7898360d26ae.png]: /images/20220829/3fe94ae8a3dd4ffdbe214ec190223822.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw%3D%3D&chksm=9bd7ea40aca06356cdb87ba86518c50646b48b8534d42625ba454c084187400b979c8d736a61&idx=1&mid=2247488584&scene=21&sn=90f7956fd9d8320fcb81aaf33c3fe7f1#wechat_redirect