分支-快排/归并---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);}
};