如何做自己網(wǎng)站的seo,兒童影樓網(wǎng)站設(shè)計(jì),什么網(wǎng)站做視頻,鄭州網(wǎng)站建設(shè)制作費(fèi)用一、題目描述二、算法原理思路#xff1a;歸并排序#xff08;降序#xff09; 雙指針如果#xff1a;nums [ cur1 ] 2 * nums[ cur2 ]#xff0c;那么證明我們還沒有找到符合題目要求的 nums[ cur ] #xff0c;所以#xff1a;cur2 如果#xff1a;nums[ cur…一、題目描述二、算法原理思路歸并排序降序 雙指針如果nums [ cur1 ] 2 * nums[ cur2 ]那么證明我們還沒有找到符合題目要求的 nums[ cur ] 所以cur2 如果nums[ cur1 ] 2 * nums[ cur2 ] 符合題目要求因?yàn)?nums[ cur1 ] 2 * nums[ cur2 ] 又因?yàn)閿?shù)組都是降序的所以 【 cur2right 】 這個區(qū)間的數(shù)字都符合題目要求。統(tǒng)計(jì)完符合題目要求的數(shù)字之后那么 cur1 看看后面數(shù)字是否有數(shù)字大于2倍的nums[ cur2 ] 那我們的 cur2 還要從頭開始判斷 nums [ cur1 ] 2 * nums[ cur2 ] 嗎答案是不用因?yàn)?cur1 沒有 之前就已經(jīng)沒有符合題目要求了nums[ cur1 ] 2 * nums[ cur2 ]cur2【mid 1cur2 - 1】因?yàn)閿?shù)組是降序的cur1 之后更加不會符合題目要了所以 cur2 不用返回?cái)?shù)組的開頭重新判斷一遍這樣會增加時(shí)間復(fù)雜度的。注意上面的內(nèi)容不能在合并數(shù)組的時(shí)候進(jìn)行在合并之前進(jìn)行因?yàn)樵诤喜⒌臅r(shí)候進(jìn)行會導(dǎo)致合并數(shù)組和找翻轉(zhuǎn)對的過程沖突所以我們要在合并數(shù)組之前進(jìn)行此時(shí)這兩個數(shù)組都是有序的。三、代碼實(shí)現(xiàn)//降序找翻轉(zhuǎn)對 class Solution { int count; public: int reversePairs(vectorint nums) { count 0; vectorint tmp; tmp.resize(nums.size()); Quicksort(0,nums.size() - 1,nums,tmp); return count; } void Quicksort(int l,int r,vectorint nums,vectorint tmp) { if(l r) return; int keyi (l r) 1; Quicksort(l,keyi,nums,tmp);//左邊【 l , keyi 】 Quicksort(keyi 1,r,nums,tmp);//右邊【keyi 1,r 】 int begin1 l,end1 keyi;//左邊數(shù)組 int begin2 keyi 1,end2 r;//右邊數(shù)組 int index l;//遍歷起始點(diǎn) int begin3 begin1,end3 end1; int begin4 begin2,end4 end2; while(begin3 end3 begin4 end4)//提前保存翻轉(zhuǎn)對 { long long tmp_i 2 * (long long)nums[begin4];//防止數(shù)據(jù)丟失 while(begin4 end4 tmp_i nums[begin3]) { begin4; tmp_i 2 * (long long)nums[begin4]; } if(begin4 end4) break; count end4 - begin4 1; begin3; } while(begin1 end1 begin2 end2)//比較遍歷 { if(nums[begin1] nums[begin2]) { tmp[index] nums[begin1]; } else { tmp[index] nums[begin2]; } } while(begin1 end1) tmp[index] nums[begin1];//把左邊剩余的數(shù)字放到 tmp while(begin2 end2) tmp[index] nums[begin2];//把右邊剩余的數(shù)字放到 tmp for(int i l;i index;i) nums[i] tmp[i];//把 tmp 里面的數(shù)字放回到原數(shù)組 nums } };//升序找翻轉(zhuǎn)對 class Solution { int count; public: int reversePairs(vectorint nums) { count 0; vectorint tmp; tmp.resize(nums.size()); Quicksort(0,nums.size() - 1,nums,tmp); return count; } void Quicksort(int l,int r,vectorint nums,vectorint tmp) { if(l r) return; int keyi (l r) 1; Quicksort(l,keyi,nums,tmp);//左邊【 l , keyi 】 Quicksort(keyi 1,r,nums,tmp);//右邊【keyi 1,r 】 int begin1 l,end1 keyi;//左邊數(shù)組 int begin2 keyi 1,end2 r;//右邊數(shù)組 int index l;//遍歷起始點(diǎn) int begin3 begin1,end3 end1; int begin4 begin2,end4 end2; while(begin3 end3 begin4 end4)//提前保存翻轉(zhuǎn)對 { while(begin3 end3 nums[begin3]/2.0 nums[begin4])//防止 5 / 2 2 2 所以不能/2 而是/2.05/2.0 2.5 2 { begin3; } if(begin3 end3) break; count end3 - begin3 1; begin4; } while(begin1 end1 begin2 end2)//比較遍歷升序 { if(nums[begin1] nums[begin2]) { tmp[index] nums[begin2]; } else { tmp[index] nums[begin1]; } } while(begin1 end1) tmp[index] nums[begin1];//把左邊剩余的數(shù)字放到 tmp while(begin2 end2) tmp[index] nums[begin2];//把右邊剩余的數(shù)字放到 tmp for(int i l;i index;i) nums[i] tmp[i];//把 tmp 里面的數(shù)字放回到原數(shù)組 nums } };