目录
一分治-快排
1颜色划分
2快速排序
3第K个最大数
4最小的k个数
二分治-归并
1归并排序
2交易逆序对的总数
3计算右侧小于当前元素的个数
4翻转对
一分治-快排
1颜色划分
oj链接：颜色分类
思路：三指针
类似双指针的移动零：搞三个指针来划分0,1,2区间
i:遍历数组(以它来分析)
left:标记0的最右侧
right:标记2的最左侧
接下来就是划分区间来讨论
class Solution {
public:void sortColors(vector<int>& nums) {int left = -1,right = nums.size();//边界处理for(int i = 0 ; i < right ; ){if(nums[i] == 0) swap(nums[++left] , nums[i++]);else if(nums[i] == 2) swap(nums[--right] , nums[i]);else i++;} }
};2快速排序
oj链接：排序数组
思路：三指针
数组分为三个区间
i:遍历数组(以它来分析)
left:标记<key的最右侧
right:标记>key的最左侧
接下来就是划分区间来讨论
优化：用随机的方式选择key值
也就是先种一颗随机数种子srand(time(NULL))
key = nums[ rand()%(r-l+1) + l ] (每次递归区间元素个数不同，l也是不同)
class Solution
{
public:vector<int> sortArray(vector<int> &nums){srand(time(NULL));QuickSort(nums, 0, nums.size() - 1);return nums;}void QuickSort(vector<int> &nums, int l, int r){if (l >= r)return;int key = nums[rand() % (r - l + 1) + l], left = l - 1, right = r + 1;for (int i = left + 1; i < right;){if (nums[i] < key)swap(nums[++left], nums[i++]);else if (nums[i] == key)i++;elseswap(nums[--right], nums[i]);}QuickSort(nums, l, left);QuickSort(nums, right, r); // r+1 x i到达r位置停止该位置的数=还是>key是不确定的！}
};3第K个最大数
oj链接：数组中的第K个最大元素
除了要用到上面的思想，还要在递归之前分类讨论！
class Solution
{
public:int findKthLargest(vector<int> &nums, int k){srand(time(NULL));return QucikSort(nums, 0, nums.size() - 1, k);}int QucikSort(vector<int> &nums, int l, int r, int k){if (l == r)return nums[l]; // l==r 保证区间是存在的!int key = nums[rand() % (r - l + 1) + l], left = l - 1, right = r + 1;for (int i = l; i < right;) // i<r X{if (nums[i] < key)swap(nums[++left], nums[i++]); // left++ Xelse if (nums[i] == key)i++;elseswap(nums[--right], nums[i]); // right-- X}int b = right - left - 1, c = r - right + 1; // b个数的区间 [left+1,right-1]if (c >= k)return QucikSort(nums, right, r, k);else if (b + c >= k)return key;elsereturn QucikSort(nums, l, left, k - b - c);}
};4最小的k个数
oj链接：库存管理 III
与上题类似，但有细节：a > k不用 a==k：因为a == k直接返回就行了不用在找了！
class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));QuickSlectSort(stock,0,stock.size()-1,cnt);return {stock.begin(),stock.begin()+cnt};}void QuickSlectSort(vector<int>& stock,int l,int r,int k){if(l>=r) return;int left=l-1,right=r+1,i=l;int key=stock[rand()%(r-l+1)+l];while(i<right){if(stock[i]<key) swap(stock[i++],stock[++left]);else if(stock[i]>key) swap(stock[i],stock[--right]);else i++;}//分情况int a=left-l+1,b=right-left-1,c=r-right+1;if(a>k) QuickSlectSort(stock,l,left,k);else if(a+b>=k) return;else QuickSlectSort(stock,right,r,k-a-b); }
};二分治-归并
1归并排序
oj链接：排序数组
class Solution {
public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());MergeSort(nums,0,nums.size()-1);return nums;}void MergeSort(vector<int>& nums,int left,int right){if(left>=right) return;//一个数向上返回int mid=left+(right-left)/2;MergeSort(nums,left,mid);MergeSort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;//i从0开始while(cur1<=mid && cur2<=right){tmp[i++]=nums[cur1]<nums[cur2]?nums[cur1++]:nums[cur2++];}while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right) tmp[i++]=nums[cur2++];for(int i=left;i<=right;i++) nums[i]=tmp[i-left];}
};2交易逆序对的总数
oj链接：交易逆序对的总数
策略：把数组分为2段区间：
1.到左区间找找逆序对后排序
2.到右区间找找逆序对后排序
3.左右区间找找逆序对后排序
可以自己画图来看看结果对不对
其实这个过程就是归并排序的过程
class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& record) {tmp.resize(record.size());return MergeSort(record,0,record.size()-1);}int MergeSort(vector<int>& record,int l,int r){if(l>=r) return 0;int mid=l+(r-l)/2;int cnt=0;cnt+=MergeSort(record,l,mid);cnt+=MergeSort(record,mid+1,r);int cur1=l,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=r){if(record[cur1]<=record[cur2]){tmp[i++]=record[cur1++];}else{//升序cnt+=mid-cur1+1;tmp[i++]=record[cur2++];}}while(cur1<=mid) tmp[i++]=record[cur1++];while(cur2<=r) tmp[i++]=record[cur2++];for(int j=l;j<=r;j++) record[j]=tmp[j-l];return cnt;}};class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& record) {tmp.resize(record.size());return MergeSort(record,0,record.size()-1);}int MergeSort(vector<int>& record,int l,int r){if(l>=r) return 0;int mid=l+(r-l)/2;int cnt=0;cnt+=MergeSort(record,l,mid);cnt+=MergeSort(record,mid+1,r);int cur1=l,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=r){if(record[cur1]<=record[cur2]){tmp[i++]=record[cur2++];}else{//降序cnt+=r-cur2+1;tmp[i++]=record[cur1++];}}while(cur1<=mid) tmp[i++]=record[cur1++];while(cur2<=r) tmp[i++]=record[cur2++];for(int j=l;j<=r;j++) record[j]=tmp[j-l];return cnt;}};3计算右侧小于当前元素的个数
oj链接：计算右侧小于当前元素的个数
解法：
1.使用上题的策略2：当前元素的后面有多少个比我小
2.关键是当前元素对应的原始数组下标我怎么知道？
有哈希表进行下标绑定？ --> 解决不了重复元素的问题
做法：用哈希表的思想创建index数组(保存元素下标)与元素进行绑定
那么在归并时就需要用到两个辅助数组进行归并
class Solution {
public:vector<int> tmpnum;vector<int> tmpindex;vector<int> ret;vector<int> index;vector<int> countSmaller(vector<int>& nums) {int n=nums.size();tmpnum.resize(n),tmpindex.resize(n);ret.resize(n),index.resize(n);for(int i=0;i<n;i++) index[i]=i;//对应下标MergeSort(nums,0,n-1);return ret;}void MergeSort(vector<int>& nums,int left,int right){if(right<=left) return;int mid=left+(right-left)/2;MergeSort(nums,left,mid);MergeSort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right)//降序{if(nums[cur1]<=nums[cur2]){tmpnum[i]=nums[cur2];tmpindex[i++]=index[cur2++];} else{ret[index[cur1]]+=right-cur2+1;tmpnum[i]=nums[cur1];tmpindex[i++]=index[cur1++];}}while(cur1<=mid){tmpnum[i]=nums[cur1];tmpindex[i++]=index[cur1++];}while(cur2<=right){tmpnum[i]=nums[cur2];tmpindex[i++]=index[cur2++];}for(int i=left;i<=right;i++){nums[i]=tmpnum[i-left];index[i]=tmpindex[i-left];}}
};4翻转对
oj链接：翻转对
与前2道题类似：注意翻转对的条件：nums[i] > 2*nums[j]
这个就不能很好的与归并排序匹配了！
但解决思路也是一样：在归并两个有序数组之前进行统计即可（就不是变合变统计）
class Solution {
public:int ret=0;vector<int> tmp;int reversePairs(vector<int>& nums) {tmp.resize(nums.size());MergeSort(nums,0,nums.size()-1);return ret;}void MergeSort(vector<int>& nums,int l,int r){if(l>=r) return;int mid=l+(r-l)/2;MergeSort(nums,l,mid);MergeSort(nums,mid+1,r);int cur1=l,cur2=mid+1,i=0;int ptr1=cur1,ptr2=cur2;while(ptr1<=mid){while(ptr2<=r&&nums[ptr1]<=2*(long long)nums[ptr2]) ptr2++;ret+=r-ptr2+1;ptr1++;}while(cur1<=mid&&cur2<=r){tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];//降序}while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=r) tmp[i++]=nums[cur2++];for(int i=l;i<=r;i++) nums[i]=tmp[i-l];}
};以上便是全部内容，有错误欢迎在评论区指正，感谢你的观看！
