【LeetCode】870 . 优势洗牌

870 . 优势洗牌

方法：贪心

思路

• 这道题的思想类似于 “田忌赛马” ，把 nums1 当成是田忌的马，nums2 当成是齐威王的马。

• 讨论田忌的下等马（nums1 的最小值）：

  • 如果它能比过齐威王的下等马（nums2 的最小值），那这一分田忌直接拿下；
  • 如果它比不过齐威王的下等马，则用田忌的下等马比齐威王的上等马（nums2 的最大值）。

• 去掉这两匹马，问题变成一个规模更小（n−1 ）的子问题。重复上述过程，即得到了所有马的对应关系。

• 代码实现时，直接对 nums1 进行排序，由于我们后续还需用用到 nums2 的下标，因此不能直接对 nums2 排序。而是用 multiset 来保存 nums2 的值和下标，同时，该数据结构会对 nums2 自动排序（从小到大），且允许存在重复值。

• 注意：erase函数的使用

  void erase ( iterator position ) ，它的参数只能是正向迭代器，我一开始使用了 rbegin() 用于删除最后一个值，而 rbegin 的类型是 reverse_iterator ，所以一直出错。

代码

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {// 创建一个答案数组vector<int> ans(nums1.size());// 先将nums1重新排序sort(nums1.begin(), nums1.end());// 创建一个多重映射，从小到大保存nums2的值及其下标// 这里需要使用multimap，因为nums2中可能存在重复的值multimap<int, int> mp;for(int i=0; i<nums2.size(); ++i){mp.insert({nums2[i], i});}for(int i=0; i<nums1.size(); ++i){// "田忌赛马" 如果nums1的最小值大于nums2的最小值，就以此赢他if(nums1[i] > mp.begin()->first){ans[mp.begin()->second] = nums1[i];mp.erase(mp.begin());}// 否则就用nums1的最小值和nums2的最大值相比else{ans[mp.rbegin()->second] = nums1[i];mp.erase(--mp.end());} }return ans;}
};

参考文献

1. 田忌赛马（Python/Java/C++/Go）