田忌赛马背后的算法

数据结构与算法
2.1k 词

前言

最近看到这么一个故事，名为田忌赛马，故事是这样的：

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

这只是三匹马对三匹马的情况，如果是一百匹呢，孙膑肯定就算不过来了，那么对于这问题，用什么算法可以解决呢？

算法分析

这个算法的主要思路是：

  • 打得过就打，打不过就用最弱的去换对面的强马

但是你也许会想：直接打得过就打的话，如果我的弱一点的马也打得过对面的马，那么战力是不是有点浪费了？

其实这样想是多此一举了，我们假设田忌的一等马为T1,二等马为T2,齐王的一等马为O1,田忌的一二等马均打得过，假设我们用T2去打对面的O1，打过了，可是你仔细一想，对面最强的已经死了，我们最强的马是为了打谁而准备的呢？所以说，这种想法根本是没必要的，就好比你考试考60分就过了，你多考几分还是没什么大用。

对于这种优势最大化问题，力扣上也有类似的，比如：【leetcode 870：优势洗牌】

给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

题目是不允许对nums2进行操作的，所以我们必须利用额外的数据结构来解决这个问题，我这里就直接用了数组来存储

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        // 获取数组长度
        int n = nums1.length;
        // 开一个二维数组，每个元素包括两个子元素，分别为在原始位置的下标和它的值
        int[][] maxpq = new int[n][2];
        // 将nums2的全部数据放入数组中
        for(int i=0;i<n;i++){
            maxpq[i][0] = i;
            maxpq[i][1] = nums2[i]; 
        }
        // 正序排nums1
        Arrays.sort(nums1);
        // 倒序排maxpq
        Arrays.sort(maxpq, (int[] p1, int[] p2)->{
            return p2[1] - p1[1];
        });
        // 设置左右指针
        int left= 0, right = n-1;
        // 设置初始下标
        int index = 0;
        // 设置生成结果用的数组
        int[] res = new int[n];
        // 遍历n次，生成结果
        while(index < n){
            // 获取子元素
            int[] pair = maxpq[index];
            // 获取子元素原来的下标与值
            int i = pair[0], maxval = pair[1];
            
            if(nums1[right] > maxval){
                // 用nums1较大的打赢对面的厉害的
                res[i] = nums1[right];
                // 右指针左移一位
                right--;
            }else{
                // 用nums1较小的换对面厉害的
                res[i] = nums1[left];
                // 左指针右移
                left++;
            }
            // 遍历用的下标+1
            index++;
        }
        // 返回结果数组
        return res;
    }
}

使用优先级队列

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        PriorityQueue<int[]> maxpq = new PriorityQueue<>((int[] p1, int[] p2) ->{
            return p2[1] - p1[1];
        });
        int n = nums1.length;
        for(int i =0;i<n;i++){
            maxpq.offer(new int[]{i,nums2[i]});
        }
        int[] res = new int[n];
        Arrays.sort(nums1);

        int left = 0, right= n-1;

        while(!maxpq.isEmpty()){
            int[] pair = maxpq.poll();
            int i = pair[0],  maxval = pair[1];
            if(nums1[right] > maxval){
                res[i] = nums1[right];
                right--;
            }else{
                res[i] = nums1[left];
                left++;
            }
        }
            return res;
    }
}

一些小疑问

为什么是res[i]?
答：i保存了其在原来时的下标，因为我们实际改的是nums1的顺序，那么我们就要按照nums2的顺序去一一对应nums1的顺序，这样才是去实现了换这个操作，不如位置不对应，我们就没有优势最大化了。

总结

这套算法的时间复杂度主要是在排序上，为O(nlogn)。
至此，这类田忌赛马的题就解决了，主要是用到了双指针技巧，从最快的马开始，比得过就比，比不过就送，这样就能对任意数量的马求取一个最优的比赛策略了。

留言