【刷题篇】分治-归并排序

文章目录

• 1、排序数组
• 2、交易逆序对的总数
• 3、计算右侧小于当前元素的个数
• 4、翻转对

1、排序数组

给你一个整数数组 nums，请你将该数组升序排列。

class Solution {
public:vector<int> tmp;void mergeSort(vector<int>& nums,int left,int right){if(left>=right)return ;int mid=(left+right)>>1;//对于非负整数，并且不产生溢出的情况下，//(left + right) >> 1 和 (left+right)/2是等价的。mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);int cur1=left,cur2=mid+1;int i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<nums[cur2]) tmp[i++]=nums[cur1++];else tmp[i++]=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];}vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);return nums;}
};

2、交易逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

class Solution {
public:int tmp[50010];int mergeSort(vector<int>& nums,int left,int right){if(left>=right)return 0;int ret=0;//计数int mid=(left+right)>>1;ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);int cur1=left,cur2=mid+1;int i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2])tmp[i++]=nums[cur1++];else{ret+=mid-cur1+1;tmp[i++]=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];return ret;}int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}
};

3、计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

class Solution {
public:vector<int> ret;vector<int> index; // 记录 nums 中当前元素的原始下标int tmpNums[500010];int tmpIndex[500010];vector<int> countSmaller(vector<int>& nums) {ret.resize(nums.size());index.resize(nums.size());for(int i=0;i<nums.size();i++)index[i]=i;mergeSort(nums,0,nums.size()-1);return ret;}void mergeSort(vector<int>& nums,int left,int right){if(left>=right)return;int mid=(left+right)>>1;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]){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}else{ret[index[cur1]]+=right-cur2+1;tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}}while(cur1<=mid){tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}while(cur2<=right){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}for(int i=left;i<=right;i++){nums[i]=tmpNums[i-left];index[i]=tmpIndex[i-left];}}
};

4、翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。

class Solution {
public:int tmp[50010];int ret=0;int reversePairs(vector<int>& nums) {mergeSort(nums,0,nums.size()-1);return ret; }void mergeSort(vector<int>& nums,int left,int right){if(left>=right)return;int mid=(left+right)>>1;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]/2.0<=nums[cur2])cur2++;else{ret+=right-cur2+1;cur1++;}}//排序是要按大小进行的并不是if(nums[cur1]/2.0<=nums[cur2])，所以就不能在一起排序，要分开cur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2])tmp[i++]=nums[cur2++];elsetmp[i++]=nums[cur1++];}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];}
};