建站网站赚钱吗,太原seo自媒体,app市场调研报告,临沂市住房和城乡建设局网站目录
一#xff0c;题目
二#xff0c;题目接口
三#xff0c;解题思路和代码
全部代码#xff1a; 一#xff0c;题目 给定两个数组nums1和nums2,nums1相对于nums2的优势可以用满足nums1[i]nums2[i]的索引i的数目来描述。 返回nums1的任意排序#xff0c;使其优…
目录
一题目
二题目接口
三解题思路和代码
全部代码 一题目 给定两个数组nums1和nums2,nums1相对于nums2的优势可以用满足nums1[i]nums2[i]的索引i的数目来描述。 返回nums1的任意排序使其优势最大化。 示例 1 输入nums1 [2,7,11,15], nums2 [1,10,4,11]
输出[2,11,7,15]示例 2 输入nums1 [12,24,8,32], nums2 [13,25,32,11]
输出[24,32,8,12] 二题目接口
class Solution {
public:vectorint advantageCount(vectorint nums1, vectorint nums2) {}
};
三解题思路和代码 这道题运用的思想其实就是一种博弈思想在历史上便是有名的田忌赛马问题的思想。 这个田忌赛马思想是这样的 1. 首先将田忌的马分为上中下等王上的马分为上中下等。 2.然后再来一个赛马赛马的思路是这样的 我的下等马肯定比不过王上的下等马所以我的下等马比不过王上的任何一匹马。 这个时候我便用我这条马把王上的上等马拖死。然后我再用我的上等马和王上的中等马赛马再用我的中等马和王上的下等马赛马。这样我们便可以赢两场取得赛马的总胜利。 将这个思想运用到我们这道题里面便是这样的一个步骤 首先以下面的示例为例 输入nums1 [12,24,8,32], nums2 [13,25,32,11] 输出[24,32,8,12] 首先我们先把nums2的下标给插入到数组Index当中。插入后是这样子的 Index[0,1,2,3]。 然后根据nums2的元素大小来对这个下标数组中的元素进行排序。 排序后便成了这个样子 Index[3,0,1,2]。 然后我们再定义一个pos指向nums1的元素left指向Index的最左元素right指向Index的最右元素。 然后便是如下的在ret数组中的插入逻辑 while(posnums1.size())//pos代表nums1的下标{if(nums1[pos]nums2[index[left]])//当nums1中选择的元素比nums2[]中的元素小的时候就插入到ret[index[right]]的位置这个下标处存放的是nums2的最大值。{ret[index[right]] nums1[pos];right--;//指向nums2的次大值下标}else{ret[index[left]] nums1[pos];//能赢便放在和nums2相对的下标处left;//指向次小值的下标}} 全部代码 class Solution {
public:vectorint advantageCount(vectorint nums1, vectorint nums2) {vectorintindex;//下标数组vectorintret(nums1.size());//结果数组for(int i 0;inums2.size();i){index.push_back(i);//将nums2的下标依次插入}sort(index.begin(),index.end(),[](int i,int j)//并且根据nums数组中的元素的大小比较规则将这个下标数组中的元素排序。{return nums2[i]nums2[j];});sort(nums1.begin(),nums1.end());//将nums1排序int left 0,right nums1.size()-1;//指向index数组的左右两端的元素int pos 0;//指向排序后的nums的下标while(posnums1.size()){if(nums1[pos]nums2[index[left]])//在ret中找到合适的位置插入nums1[pos]{ret[index[right]] nums1[pos];right--;}else{ret[index[left]] nums1[pos];left;}}return ret;//返回结果}
};
