襄阳集团网站建设,音乐网站样式设计,微信公众号建设公司,学校网站怎么做目录
1.升序#xff08;以右边的合并组为基准#xff09;
2.降序#xff08;以左边的合并组为基准#xff09; 3.逆对序--固定下标
1.升序#xff08;以右边的合并组为基准#xff09;
找出左边有多少个数比我(nums[right])大
应该在每一次合并之前#xff0c;进行…目录
1.升序以右边的合并组为基准
2.降序以左边的合并组为基准 3.逆对序--固定下标
1.升序以右边的合并组为基准
找出左边有多少个数比我(nums[right])大
应该在每一次合并之前进行逆序对查找每一个该合并的组都是按升序排列所以当nums[left]nums[right]时应该left因为都是升序所以当nums[left]nums[right]right时left从当前位置不动。 class Solution {
public:vectorint ret;int vim0;int reversePairs(vectorint record) {ret.resize(record.size());mergesort(record,0,record.size()-1);return vim;}void merge(vectorintnums,int low,int high,int mid){int leftlow,rightmid1, i0;while(leftmidrighthigh){if(nums[left]nums[right]) ret[i]nums[left];else {ret[i]nums[right];vim(mid1-left);}}while(leftmid) ret[i]nums[left];while(righthigh) ret[i]nums[right];for(int i0;ihigh-low1;i){nums[ilow]ret[i];}}void mergesort(vectorintnums,int low,int high){if(lowhigh) return;int mid(lowhigh)/2;mergesort(nums,low,mid);mergesort(nums,mid1,high);merge(nums,low,high,mid);}
};
2.降序以左边的合并组为基准 找出多少个数比我小 合并过程 class Solution {
public:vectorint ret;int vim0;int reversePairs(vectorint record) {ret.resize(record.size());mergesort(record,0,record.size()-1);return vim;}void merge(vectorintnums,int low,int high,int mid){int leftlow,rightmid1, i0;while(leftmidrighthigh){if(nums[left]nums[right]) {vim(high-right1);ret[i]nums[left];}else {ret[i]nums[right];}}while(leftmid) ret[i]nums[left];while(righthigh) ret[i]nums[right];for(int i0;ihigh-low1;i){nums[ilow]ret[i];}}void mergesort(vectorintnums,int low,int high){if(lowhigh) return;int mid(lowhigh)/2;mergesort(nums,low,mid);mergesort(nums,mid1,high);merge(nums,low,high,mid);}
}; 对比 降序升序 void merge(vectorintnums,int low,int high,int mid) { int leftlow,rightmid1, i0; while(leftmidrighthigh) { if(nums[left]nums[right]) { vim(high-right1); ret[i]nums[left]; } else ret[i]nums[right]; } while(leftmid) ret[i]nums[left]; while(righthigh) ret[i]nums[right]; for(int i0;ihigh-low1;i) { nums[ilow]ret[i]; } } void merge(vectorintnums,int low,int high,int mid) { int leftlow,rightmid1, i0; while(leftmidrighthigh) { if(nums[left]nums[right]) ret[i]nums[left]; else { ret[i]nums[right]; vim(mid1-left); } } while(leftmid) ret[i]nums[left]; while(righthigh) ret[i]nums[right]; for(int i0;ihigh-low1;i) { nums[ilow]ret[i]; } } 3.逆对序--固定下标
增加一个下标数据和交换下标数组当交换数组发生数据交换时交换下标数组也要发生数据交换 class Solution {vectorint tempnums,index,tempindex,count;
public:vectorint countSmaller(vectorint nums) {int nnums.size();tempnums.resize(n);//交换数组tempindex.resize(n);//交换下标index.resize(n);//存放原始下表count.resize(n);//存放结果for(int i0;in;i) index[i]i;mergesort(nums,0,n-1);return count;}void merge(vectorintnums,int low,int high,int mid){int leftlow,rightmid1,i0;while(leftmidrighthigh){if(nums[left]nums[right]) {tempnums[i]nums[left];tempindex[i]index[left];count[index[left]](high-right1);i;left;}else{tempindex[i]index[right];tempnums[i]nums[right];i;right;}}while(leftmid){tempnums[i]nums[left];tempindex[i]index[left];i;left;}while(righthigh){tempindex[i]index[right];tempnums[i]nums[right];i;right;}for(int j0;ji;j){nums[jlow]tempnums[j];index[jlow]tempindex[j];}}void mergesort(vectorintnums,int low,int high){if(lowhigh) return ;int mid(lowhigh)1;mergesort(nums,low,mid);mergesort(nums,mid1,high);merge(nums,low,high,mid);}
};
