田忌赛马背后的算法决策 :: labuladong的算法小抄

[labuladong]

文章链接点这里：田忌赛马背后的算法决策

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

[Alwin4Zhang]

870. 优势洗牌（中等） python version

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 田忌赛马问题
        hq = []
        # 大顶堆
        for i, num in enumerate(nums2):
            heapq.heappush(hq, (-num, i))
        nums1.sort()
        # 双指针
        left, right = 0, len(nums1) - 1
        res = [0] * len(nums1)
        while hq:
            max_num, idx = heapq.heappop(hq)
            max_sum = -max_num
            if max_sum < nums1[right]:
                res[idx] = nums1[right]
                right -= 1
            else:
                res[idx] = nums1[left]
                left += 1
        return res

[saw008]

Python解法，空间使用超过99%+，没有用到堆，只用了二分搜索和排序

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        def helper(idx):
            left, right = 0, len(nums1)-1
            while left <= right:
                mid = (left + right) // 2
                if nums1[mid] > nums2[idx]:
                    right = mid - 1
                else:
                    left = mid + 1
            if left < len(nums1):
                temp = left
            else:
                temp = 0
            ans.append(nums1[temp])
            nums1.pop(temp)
            
        nums1.sort()
        visited = [False] * len(nums1)
        ans = []
        for i in range(len(nums2)):
            helper(i)
        return ans

[miiiiiko]

没懂，既然都pop了这个visited数组是干啥用的呀，而且.pop(i)方法平均时间复杂度是O(n)吧

[NCUCyy]

99%空间，5%时间 😭

[Xiaoyuan-Liu]

try this case:
[2,0,4,1,2]
[1,3,0,0,2]

[Moneylijin]

感觉这个有两个答案，
[2,4,1,2,0]和
[2,0,2,1,4]都可以我感觉，还是我没有看懂题目

[labuladong]

没问题，这道题的答案并不唯一

[labuladong]

@Xiaoyuan-Liu 没问题，这道题的答案并不唯一

[LakersHao]

有一个小问题，就是PriorityQueue的构造方法为啥可以只有比较器，我一直没找到这种构造方法，但是我看网上都是直接用的，困扰我好久了

[XiaoFang222]

@LakersHao java的话建议直接按住ctrl点进PriorityQueue的源码，可以看到有7个构造器，其中有一个是
public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); }

[fakeyanss]

这个case没过

[fakeyanss]

go实现，大顶堆解法会有一个case不通过，换成sort直接两边排序可以ac

import (
	"container/heap"
	"sort"
)

// @lc code=start
func advantageCount(nums1 []int, nums2 []int) []int {
	// sort.Ints(nums1)
	// b := make([][2]int, len(nums2))
	// for i, n := range nums2 {
	// 	b[i] = [2]int{n, i}
	// }
	// sort.Slice(b, func(i, j int) bool {
	// 	return b[i][0] < b[j][0]
	// })

	// result := make([]int, len(nums1))
	// left, right := 0, len(nums1)-1
	// for i := len(b) - 1; i >= 0; i-- {
	// 	val, idx := b[i][0], b[i][1]
	// 	if nums1[right] > val {
	// 		result[idx] = nums1[right]
	// 		right--
	// 	} else {
	// 		result[idx] = nums1[left]
	// 		left++
	// 	}
	// }
	// return result
	// nums1 升序排列
	sort.Ints(nums1)

	// nums2 降序排序，大顶堆
	h := make(IntHeap, 0)
	for i, val := range nums2 {
		h = append(h, []int{i, val})
	}
	heap.Init(&h)

	l, r := 0, len(nums1)-1
	res := make([]int, len(nums1))
	for h.Len() > 0 {
		pair := h.Pop()
		i, max := (pair.([]int))[0], (pair.([]int))[1]
		if max < nums1[r] {
			// 如果nums1[r]大于max，那就填入这个值
			res[i] = nums1[r]
			r--
		} else {
			// 否则用最小最混一下，田忌赛马
			res[i] = nums1[l]
			l++
		}
	}
	return res
}

// 大顶堆，实现heap的interface
// h[x][0] 存储 index，h[x][1] 存储 value
type IntHeap [][]int

// 绑定Len方法
func (h IntHeap) Len() int {
	return len(h)
}

// 绑定Less方法，这里用的是小于号，生成的是小根堆
func (h IntHeap) Less(i, j int) bool {
	return h[i][1] > h[j][1]
}

// 绑定swap方法
func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

// pop、push 使用指针，因为改变了slice长度
// 绑定put方法，将index置为-1是为了标识该数据已经出了优先级队列了
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[0]
	*h = old[1:n]
	return item
}

// 绑定push方法
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.([]int))
}

// @lc code=end

[XXFong]

heap API用错了，h.Pop()应该是改为heap.Pop(&h)

[VincentWang1024]

不用PQ可以么，直接Desend排序nums2?

[yonggui-yan]

打卡
先排序，然后从大到小，比得过就比，比不过就用最差的。
注意nums2排序方式

[SUN7700]

相等的情况呢？如果田忌是【8，6】，齐王是【8，7】，那么8=8的时候换6来打是可以的，优势增大；如果齐王是【8，5】呢，那样本来可以平一局赢一局的，结果变成输一局赢一局，优势减小了吧。所以相等情况是不是要根据下一个的值大小比较来确定顺序

[SUN7700]

噢噢噢好像跟田忌赛马还是有点区别，田忌赛马才是计分，这题优势是只需要让nums1[i] > nums2[i] 的次数最多就好了

[SUN7700]

计分模式的代码好像有点复杂，难搞

[labuladong]

很细节👍 如果是计分模式确实会复杂一些，这里面的核心难点是，有时候平局可能会得到更好的总分。我想到一个比较简单的解决方案供你参考：你执行两次算法，第一次算法中，出现平局时依然换差马上来送人头；第二次算法中，出现平局时不要送人头。最后再比较一下两种结果哪个的总分更高。这样虽然重复执行了几次算法，但 big O 的时间复杂度依然和之前一样，也可以解决包含平局的场景。

[xiaoyuming233]

个人感觉跑两遍算法不行，比如[8,6,18,16,28,26,38,36,48,46],和[8,5,18,17,28,25,38,35,48,47],每两个相邻的数都会产生一次平局的情况判定，一味地送人头或者保平局都不能达到最优解。比较理想的情况是像前面这个例子一样，每次平局带来的影响“相互独立”，所以可以对每次平局单独判定，但如果情况更加复杂的话，这种当前的最优解不一定会带来整体的最优解的情况，应该需要用到动态规划算法来解决。

[guqihao-7]

在看文章前尝试自己做了下这道题，对于排序后导致顺序错乱问题，可以写一个类来解决。对于两组马都按照战力值升序排列：

class Solution {
        class Horse {
            int pos, weight;
            boolean used;
        }
        
        public int[] advantageCount(int[] nums1, int[] nums2) {
            int n = nums1.length;
            int[] ans = new int[n];
            Horse[] horses1 = new Horse[n];
            Horse[] horses2 = new Horse[n];
            for (int i = 0; i < n; i++) {
                horses1[i] = new Horse();
                horses1[i].pos = i;
                horses1[i].weight = nums1[i];

                horses2[i] = new Horse();
                horses2[i].pos = i;
                horses2[i].weight = nums2[i];
            }

            Arrays.sort(horses1, Comparator.comparingInt(o -> o.weight));
            Arrays.sort(horses2, Comparator.comparingInt(o -> o.weight));
            int p1 = 0, p2 = 0;
            while (p1 < n) {
                if (horses1[p1].weight > horses2[p2].weight) {
                    ans[horses2[p2].pos] = horses1[p1].weight;
                    horses1[p1].used = true;
                    horses2[p2].used = true;
                    p1++; p2++;
                } else {
                    p1++;
                }
            }
            p2 = n - 1;
            // 从后往前找
            for (int i = horses1.length - 1; i >= 0; i--) {
                if (!horses1[i].used) {
                    while (ans[horses2[p2].pos] != 0) p2--;
                    ans[horses2[p2].pos] = horses1[i].weight;
                }
            }
            return ans;
        }
    }

[ManofDiligence]

C++ 版本，這樣也可以，used 這個Boolean 變量是不需要，只需對馬horse這個類(或用c++ 的struct)的戰力進行排序然後用雙指針的方法比較就可以了
class Solution {
private:
struct horse{
int pos, power;
};

struct compare{
    bool operator()(horse a, horse b){
        
        return a.power < b.power;

    }
};

public:

vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2){
    int n = nums1.size();
    vector<horse> h1(n);
    vector<horse> h2(n);
    for(int i=0; i<n; i++){
        h1[i].pos = i;
        h1[i].power = nums1[i];
        h2[i].pos = i;
        h2[i].power = nums2[i];
        
    }
    sort(h1.begin(), h1.end(), compare());
    sort(h2.begin(), h2.end(), compare());
    vector<int> res(n);
    
    int s = 0, b = n-1;
    int i = n-1;
    while(s<=b&&i>=0){
        if(h1[b].power>h2[i].power){
            res[h2[i].pos] = h1[b].power;
            b--;
        }
        else{
            res[h2[i].pos] = h1[s].power;
            s++;
        }
        i--;
    }

    return res;
    
}

};

[fantian007]

Test Case

[2,0,4,1,2]
[1,3,0,0,2]

我的
[1,4,0,2,2]

答案
[2,0,2,1,4]

#我的不比答案好？还是有什么我遗漏了？

[xmuzhl]

条件是大于，并非大于等于

[Moneylijin]

我的
[2,4,1,2,0]
答案
[2,0,2,1,4]
请问这个怎么算

[run123love]

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1_ = sorted(nums1)
        nums2_ = sorted(enumerate(nums2), key=lambda p: p[1])
        
        left = 0
        right = len(nums1) - 1
        res = [-1] * len(nums1)

        while nums2_:
            i, maxval = nums2_.pop()
            if maxval < nums1_[right]:
                res[i] = nums1_[right]
                right -= 1
            else:
                res[i] = nums1_[left]
                left += 1

        return res

[bruceeewong]

20230110 打卡。田忌赛马的思想真牛

[BlackhawkZZH]

js写法,时间复杂度O(nlogn)

var advantageCount = function(nums1, nums2) {
    let map = {} //记nums2对应的nums1
    let res = [] //放return结果
    let nums2Copy = [...nums2] //存一下原来nums2的顺序
    nums1.sort((a, b) => (b - a))
    nums2.sort((a, b) => (b - a))
    for(let i = 0; i < nums2.length; i++){
        let temp = nums1.shift() //找nums1最快的🐴
        if(!map[nums2[i]]) map[nums2[i]] = [] //防止nums2有重复值用list存
        if(nums2[i] >= temp){   //nums2🐴更快
            nums1.unshift(temp) //nums1最快的留着以后用
            map[nums2[i]].push(nums1.pop()) //放个最小的nums1🐴
        }
        else map[nums2[i]].push(temp) //放nums1最快🐴
    }
    for(let i = 0; i < nums2Copy.length; i++){
        res.push(map[nums2Copy[i]].pop()) //按照原来nums2的顺序排一下对应的nums1位置
    }
    return res
};

[whale2002]

超时了

[heeler-deer]

优势洗牌里面chatgpt给出的c++解法有问题，一是语法错误（priority_queue在插入数据时没有make_pair），二是没有重载运算符，导致priority_queue进行排序时按照第一个数字i排序，

/*
 * @lc app=leetcode.cn id=870 lang=cpp
 *
 * [870] 优势洗牌
 */

// @lc code=start
class Solution {
public:
  vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2) {
    
    priority_queue<pair<int, int>> maxpl;
    for (int i = 0; i < nums1.size(); i++) {
      maxpl.push(make_pair(nums2[i],i));
    }
    int left = 0, right = nums1.size() - 1;
    vector<int> res(nums1.size());
    sort(nums1.begin(), nums1.end());
    while (!maxpl.empty()) {
      auto [maxp,i] = maxpl.top();
      maxpl.pop();
      if (nums1[right] > maxp) {
        res[i] = nums1[right];
        cout<<res[i]<<maxp<<i<<endl;
        
        right--;
      } else {
        
        res[i] = nums1[left];
cout<<res[i]<<maxp<<i<<endl;
        left++;
      }
    }
    return res;
  }
};
// @lc code=end

[zc627788]

chatgpt给出的js解法前半部分有些问题, 更正了下

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var advantageCount = function (nums1, nums2) {
    // nums1和nums2长度一致, 选其一
    let n = nums2.length

    const arr = new Array(n).fill(0).map((_, i) => i)   //数组[0,1,2,3...]
    arr.sort((a, b) => nums2[a] - nums2[b])  //根据num2升序后的数组索引,比如 nums2 = [1,10,4,11] , arr排序后的  [0,2,1,3]，  0代表nums2中的1, 2代表nums2中4  1代表代表nums2的10 ....
    const finArr = arr.map(item => [item, nums2[item]])   //把索引与当前nums2的值对应

    // 排序nums1
    nums1.sort((a, b) => a - b)

    // 双指针
    let left = 0, right = n - 1

    // 最终结果
    const res = []

    while (finArr.length > 0) {
        // 每次获取num2的最大值索引和值
        const num2Max = finArr.pop()
        let index = num2Max[0], maxValue = num2Max[1]
        //  当前nums1的最大值和nums2的最大值比较，把num2的对应位置的索引(index)替换成nums1,给到最终结果
        if (nums1[right] > maxValue) {
            // 如果nums1的比num2的大，把num1最大值给到对应索引
            res[index] = nums1[right]
            right--
        } else {
              // 如果nums1的比num2的小， 把num1最小值给到对应索引
            res[index] = nums1[left]
            left++
        }

    }
    return res
};

[EyeDroplyq]

打卡，附上详细注解的Java代码

    //算法的思路其实很简单：如果我们两个最好的比较nums1可以干过nums2，那就让nums1最好的上，否则让nums1中最差的去送人头
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n=nums1.length;
        //对nums1进行一个排序，升序排列
        Arrays.sort(nums1);
        //因为nums2是不能改变顺序的，我们是和nums2进行对弈的，所以使用一个辅助数据结构来存储排序的结构
        //优先级队列中自定义了比较规则从大到小排列了，每个节点存储的结构是[索引，值]
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((int[] pair1, int[] pair2) -> {
            return pair2[1] - pair1[1];
        });
        for (int i = 0; i < nums2.length; i++) {
            priorityQueue.offer(new int[]{i,nums2[i]});
        }

        //两个人开始对弈
        int left=0,right=n-1;
        int[] res=new int[n];
        while(!priorityQueue.isEmpty()){
            int[] poll = priorityQueue.poll();
            if(nums1[right]>poll[1]){
                //nums1中最好的可以打过nums2中最好的，直接干
                //结果的位置要根据nums2的索引顺序来确定，因为是和nums2进行对弈的
                res[poll[0]]=nums1[right];
                right--;
            }else{
                //干不过，让最差的去送
                res[poll[0]]=nums1[left];
                left++;
            }
        }
        return res;
    }

[handsomelys]

补充一个cpp的版本，东哥这里的cpp版本答案有点偏差：

[handsomelys]

我擦 怎么代码格式错了 补一下。。

class Solution {
public:
    struct cmp1 {
        bool operator()(const pair<int, int>&a, const pair<int, int> &b) {
            return a.second < b.second;
        }
    };
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();

        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp1> pq;
        for (int i = 0; i < n; i++) {
            pq.emplace(i, nums2[i]);
        }
        
        sort(nums1.begin(), nums1.end());


        vector<int> res(n);
        int left = 0, right = n - 1;
        while (!pq.empty()) {
            auto [i, maxval] = pq.top();
            pq.pop();
            if (nums1[right] > maxval) {
                res[i] = nums1[right];
                right--;
            } else {
                res[i] = nums1[left];
                left++;
            }
        }
        return res;
    }
};

[fengyeuuu]

变复杂了 直接交换i和nums2[i] 进队列的顺序就行 优先级队列本身就是大根堆 不需要重载

[fengyeuuu]

博主的c++代码存在错误，maxpq的顺序因为nums2[i],i 因为队列以第一个元素排大小。

[Feezhen]

更新一下pass的cpp代码，如果用chatgpt翻译过来的cpp不太正确。
代码：

class Solution {
public:
    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(nums2[i] , 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 [maxval, i] = maxpq.top();
            maxpq.pop();
            if (maxval < nums1[right]) {
                // 如果 nums1[right] 能胜过 maxval，那就自己上
                res[i] = nums1[right];
                right--;
            } else {
                // 否则用最小值混一下，养精蓄锐
                res[i] = nums1[left];
                left++;
            }
        }
        return res;
    }
};

[shiboys]

妙哉，妙哉

[Feezhen]

非常感谢您的邮件。

[Feezhen]

非常感谢您的邮件。

[xiaoyuming233]

我想到的思路是从最差的马开始找，各自从所有未分配比赛的马中找一匹最差的马，如果田忌能赢，就用这匹马，这样用最差的马来获取胜利是最“节约“的办法。如果田忌不能赢，因为这匹马必然不会带来任何一场胜利，因此就让他去与齐王最厉害的马比赛，然后再比较当前田忌最差的马能否嬴齐王最差的马，以此类推，直到所有的马都被分配比赛。

[Feezhen]

非常感谢您的邮件。

[hualuo321]

cpp的代码错了，因为优先队列没有自定义排序
class Solution {
public:
struct comp {
bool operator() (const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
}
};
vector advantageCount(vector& nums1, vector& nums2) {
int n = nums1.size();
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
for (int i = 0; i < n; ++i) {
pq.push({i, nums2[i]});
}
sort(nums1.begin(), nums1.end(), [](int a, int b){return a > b;});
vector res(n, 0);
// 双指针
int left = 0, right = n - 1;
while (!pq.empty()) {
auto cur = pq.top();
pq.pop();
cout << cur.second << " ";
if (cur.second < nums1[left]) {
res[cur.first] = nums1[left];
left++;
} else {
res[cur.first] = nums1[right];
right--;
}
}
return res;
}
};

[Feezhen]

非常感谢您的邮件。