分支-快排/归并---1
目录
1.排序数组
2.数组中的第K个最大元素
3.最小k个数
4.排序数组（归并）
5.数组中的逆序对
6.计算右侧小于当前元素的个数
7. 翻转对
1.排序数组
快排的写法有很多，这里我采取了相对快的三路划分加随机基准值。
三路划分，是将一段区间划成了【小于基准值】【等于基准值】【大于基准值】的三段区间。递归遍历的时候只需要递归【小于基准值】【大于基准值】的区间，中间区间就可以看作已经完成了排序，这也与二路划分的快排有很大区别，相比之下遇到极端情况（整个区间都是同一个数字）时间复杂度会更小。
考虑到三路划分本身不是很难，但是这边还是有基础题的。
75. 颜色分类 - 力扣（LeetCode）
class Solution { public:void sortColors(vector<int>& nums) {int n=nums.size();int left=-1,right=n;int index=0;while(index<right){if(nums[index]==0){swap(nums[++left],nums[index++]);}else if(nums[index]==1)index++;else if(nums[index]==2){swap(nums[--right],nums[index]);}}}};283. 移动零 - 力扣（LeetCode）//这题是二路的，但是思想跟三路很像，主要是学会怎么划分，具体是几路要看题目要求
void moveZeroes(int* nums, int numsSize) {int dest=-1,cur=0;while(cur<numsSize){if(nums[cur]!=0){dest++;int tmp=nums[dest];nums[dest]=nums[cur];nums[cur]=tmp;}cur++;} }912. 排序数组 - 力扣（LeetCode）
class Solution { public: //返回随机基准值int rad(vector<int>&nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left];} //快排本身void fastsort(vector<int>&nums,int left,int right){if(left>=right)return;//递归出口int mid=rad(nums,left,right);//获取基准值int l=left-1,r=right+1,index =left;//设定三指针，方便划分3路while(index<r){if(nums[index]<mid)swap(nums[index++],nums[++l]);else if(nums[index]==mid)index++;else if(nums[index]>mid)swap(nums[index],nums[--r]);}fastsort(nums,left,l);fastsort(nums,r,right);}vector<int> sortArray(vector<int>& nums) {int n=nums.size();srand(time(0));fastsort(nums,0,n-1); return nums;} };
2.数组中的第K个最大元素
215. 数组中的第K个最大元素 - 力扣（LeetCode）
class Solution { public: //返回随机基准值int rad(vector<int>&nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left];} //快排int qsort(vector<int>&nums,int left,int right,int k){ //结合最下面的条件判断，我们会发现，我们只会进入，至少有一个元素的区间， //所以最多就是left==right，我们在寻找最有可能的区间中，一直找，找到只有 //一个元素，说明正好就是他了if(left==right)return nums[left]; //三路划分int mid=rad(nums,left,right);int index=left,l=left-1,r=right+1;while(index<r){if(nums[index]<mid)swap(nums[index++],nums[++l]);else if(nums[index]==mid)index++;else swap(nums[index],nums[--r]);} //a是【小于基准值】的个数，b是【等于基准值】的个数，c是【大于基准值】的个数int a=l-left+1,b=r-l-1,c=right-r+1; //c>=k，说明第k大的数一定在【大于基准值】区间里，所以只需要递归这个区间即可if(c>=k){return qsort(nums,r,right,k);} //在不满足c>=k的情况，b+c>=k，说明我们要找的第k大数，正好就是当前的基准值 //直接返回基准值即可else if(b+c>=k)return mid; //在不满足上面条件的情况下，因为k肯定是小于整个区间大小的，那么b+c<k，说明a+b+c>=k， //那么此时第k大的数就在【小于基准值】区间内，注意了，前面两个条件，k都是原始的k //那是因为可以确定【等于基准值】区间元素个数+【大于基准值】区间元素个数大于k个或 //【大于基准值】区间元素个数大于k个，所以k一定是在left-right区间内的 //但这里不同，虽然我们可以判断第k大数在【小于基准值】区间内， //但是这个区间元素不一定大于等于k个，所以，我们传参的时候，是在 //【小于基准值】区间内找第k-b-c大的数else{return qsort(nums,left,l,k-b-c);}}int findKthLargest(vector<int>& nums, int k) {int n=nums.size();srand(time(NULL));return qsort(nums,0,n-1,k);} };3.最小k个数
面试题 17.14. 最小K个数 - 力扣（LeetCode）
class Solution { public:int rad(vector<int>& arr,int l,int r){return arr[rand()%(r-l+1)+l];}void dfs(vector<int>& arr,int l,int r,int k){if(l>=r)return ;int key=rad(arr,l,r);int left=l-1,right=r+1,index=l;while(index<right){if(arr[index]<key)swap(arr[index++],arr[++left]);else if(arr[index]==key)index++;else swap(arr[index],arr[--right]);}int a=left-l+1,b=right-1-left,c=r-right+1; //a>k，说明，最小k个数一定在【小于基准值】的区间里。所以要继续递归a的区间 //然后三路划分a区间，重复操作，直到满足第二个条件。 //如果满足a+b>=k，那么不管是a==k，还是a+b==k，都说明此时数组前k个数已经是最小的k个数了 //直接返回即可 //如果前两个条件都不满足，说明这k个数是包含了a和b，包含了部分c，所以要继续递归c的区间 //然后三路划分c区间，重复操作，直到满足第二个条件。if(a>k)dfs(arr,l,left,k);else if(a+b>=k)return ;else dfs(arr,right,r,k-a-b);}vector<int> smallestK(vector<int>& arr, int k) {srand(time(NULL));dfs(arr,0,arr.size()-1,k);vector<int>res(k);for(int i=0;i<k;i++)res[i]=arr[i];return res;} };4.排序数组（归并）
912. 排序数组 - 力扣（LeetCode）
class Solution { public:void merge(vector<int>&num,int l,int r){if(l>=r)return;int mid=l+(r-l)/2;merge(num,l,mid);merge(num,mid+1,r);int i1=l,i2=mid+1;int i3=0;while(i1<=mid&&i2<=r){if(num[i1]<num[i2]){tmp[i3++]=num[i1++];}else tmp[i3++]=num[i2++];}while(i1<=mid)tmp[i3++]=num[i1++];while(i2<=r)tmp[i3++]=num[i2++];for(int i=l;i<=r;i++)num[i]=tmp[i-l];return ;}vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());merge(nums,0,nums.size()-1);return nums;}vector<int>tmp; };
5.数组中的逆序对
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
思路依旧是归并。
整个数组，我们可以这样思考。一段区间的逆序对，如果以中间划分，可以分为【左部分】的逆序对个数+【右部分】的逆序对个数+【左部分挑一个,右部分挑一个】的逆序对个数
由此，我们可以以分治的思路，一路切割。
注意，【左部分挑一个,右部分挑一个】这部分必须要依靠排序来快速挑选，否则，时间复杂度依旧是On2。
也就是说可以分为【左部分】的逆序对个数&&排序+【右部分】的逆序对个数&&排序+【左部分挑一个,右部分挑一个】的逆序对个数&&排序。
#include <cstdio> class Solution { public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型vector * @return int整型*/int tmp[100010]={0};int _InversePairs(vector<int>& nums,int l,int r){if(l>=r)return 0;//说明当前区间只有1或0个数字，没有逆序对，返回0int mid=l+(r-l)/2;int res=0;res+=_InversePairs(nums,l , mid);//加左部分res+=_InversePairs(nums, mid+1, r);//加右部分res%=1000000007;//题目数据要求，必须mod，不然有个样例会溢出int cur1=l,cur2=mid+1;int i=l;while(cur1<=mid&&cur2<=r)//排序和找逆序对，同时进行{if(nums[cur1]>nums[cur2])//说明自cur2坐标上起的数字，都是比cur1坐标上的值小{res+=(r-cur2+1);tmp[i++]=nums[cur1++];}else {tmp[i++]=nums[cur2++];}}//sort(nums.begin()+l,nums.begin()+r+1,greater<int>()); //注意，偷懒可以直接sort，但是时间复杂度很高，因为sort是Nlogn,而我们自己写 //有序数组合并，可以做到Onwhile(cur1<=mid)tmp[i++]=nums[cur1++];while(cur2<=r)tmp[i++]=nums[cur2++];for(int k=l;k<=r;k++)nums[k]=tmp[k];return res%1000000007;}int InversePairs(vector<int>& nums) {return _InversePairs(nums,0,nums.size()-1);}};
6.计算右侧小于当前元素的个数
315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
这题，跟上一题很像。
我们需要两个额外的数组，一个是用来记录数字在原数字中的下标，在排序时同步移动
，一个是用来记录答案的数组。利用第一个数组，即可下标访问，及时更新第二个数组
class Solution { public:void merge(vector<int>& nums,int l,int r,vector<int>&res){if(l>=r)return;int mid=l+(r-l)/2;merge(nums,l,mid,res);merge(nums,mid+1,r,res);int cur1=l,cur2=mid+1,index=l;while(cur1<=mid&&cur2<=r){if(nums[cur1]>nums[cur2]){res[ix[cur1]]+=(r-cur2+1);tmp[index]=nums[cur1];tmp1[index++]=ix[cur1++];}else{tmp[index]=nums[cur2];tmp1[index++]=ix[cur2++];}}while(cur1<=mid)tmp[index]=nums[cur1],tmp1[index++]=ix[cur1++];while(cur2<=r)tmp[index]=nums[cur2],tmp1[index++]=ix[cur2++];for(int i=l;i<=r;i++)nums[i]=tmp[i],ix[i]=tmp1[i];}vector<int> countSmaller(vector<int>& nums) {int n=nums.size();for(int i=0;i<n;i++)ix[i]=i;vector<int>res(n,0);merge(nums,0,n-1,res);return res;}int ix[100100]={0};int tmp[100100]={0};int tmp1[100100]={0}; };
7. 翻转对
493. 翻转对 - 力扣（LeetCode）
这题，跟上面逆序对的写法，几乎一模一样，只是要注意，排序必须单独写，不能在找逆序对里同时排序。还有条件是>2倍(虽然每个数都是int范围，但是*2可能会溢出，所以可以强转成更大的类型，比如long,或者判断条件可以是a>=b/2.0，注意c++/是整除，可能有余数，所以要加个2.0，这样就是浮点数了)
class Solution { public:int tmp[100010] = { 0 };int _InversePairs(vector<int>& nums, int l, int r){if (l >= r)return 0;//说明当前区间只有1或0个数字，没有逆序对，返回0int mid = l + (r - l) / 2;int res = 0;res += _InversePairs(nums, l, mid);//加左部分res += _InversePairs(nums, mid + 1, r);//加右部分int cur1 = l, cur2 = mid + 1;int i = l;while (cur1 <= mid && cur2 <= r)//排序和找逆序对，同时进行{if (nums[cur1] > 2*(long)nums[cur2])//说明自cur2坐标上起的数字，都是比cur1坐标上的值小{res += (r - cur2 + 1);cur1++;}else {cur2++;}}int l1=l,l2=mid+1;while(l1<=mid&&l2<=r){if(nums[l1]>nums[l2]){tmp[i++]=nums[l1++];}else{tmp[i++]=nums[l2++];}}while(l1<=mid)tmp[i++]=nums[l1++];while(l2<=r)tmp[i++]=nums[l2++];for(int k=l;k<=r;k++)nums[k]=tmp[k];return res;}int InversePairs(vector<int>& nums) {return _InversePairs(nums, 0, nums.size() - 1);}int reversePairs(vector<int>& nums) {return InversePairs(nums);} };