做一个购物网站多少钱,江阴市住房和城乡建设局网站,网站建设主管,都江堰最新新闻头条870 . 优势洗牌 方法#xff1a;贪心
思路 这道题的思想类似于 “田忌赛马” #xff0c;把 nums1 当成是田忌的马#xff0c;nums2 当成是齐威王的马。 讨论田忌的下等马#xff08;nums1 的最小值#xff09;#xff1a; 如果它能比过齐威王的下等马#xff08;nums…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:vectorint advantageCount(vectorint nums1, vectorint nums2) {// 创建一个答案数组vectorint ans(nums1.size());// 先将nums1重新排序sort(nums1.begin(), nums1.end());// 创建一个多重映射从小到大保存nums2的值及其下标// 这里需要使用multimap因为nums2中可能存在重复的值multimapint, int mp;for(int i0; inums2.size(); i){mp.insert({nums2[i], i});}for(int i0; inums1.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
