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;}
};
参考文献
- 田忌赛马(Python/Java/C++/Go)