做国产免费视频网站,青海城乡建设厅网站 官网,昆明网站建设精英,sql注入 WordPress文章目录 #x1f33c;0. 归并排序#x1f33b;1. 题目#x1f33c;2. 算法原理#x1f337;3. 代码实现 #x1f33c;0. 归并排序
归并排序是典型的分治#xff0c;将数组分成若干个子数组#xff0c;数组两两比较#xff0c;不是很清楚的#xff0c;可以查看此篇文… 文章目录 0. 归并排序1. 题目2. 算法原理3. 代码实现 0. 归并排序
归并排序是典型的分治将数组分成若干个子数组数组两两比较不是很清楚的可以查看此篇文章——数据结构——七大排序
这里以力扣912. 排序数组为例
class Solution {vectorint tmp;
public:vectorint sortArray(vectorint nums){tmp.resize(nums.size());mergeSort(nums, 0, nums.size()-1);return nums;}void mergeSort(vectorint nums, int left, int right){if(left right) return;int mid left (right-left)/2;//[left,mid] [mid1,right]mergeSort(nums,left,mid);mergeSort(nums,mid1,right);//合并int i 0,cur1 left,cur2 mid1;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];}
};1. 题目 题目链接LCR 170. 交易逆序对的总数 在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录 record返回其中存在的「交易逆序对」总数。
示例 1:
输入record [9, 7, 5, 4, 6]
输出8
解释交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。限制
0 record.length 500002. 算法原理
逆序对的意思就是从数组中挑2个数前面的数大于后面的数 且 前一个数的下标小于后一个数的下标然后查看有几对
解法一暴力枚举
固定一个数找后面的区间两层for循环即可但是这个题目的等级是困难对于力扣的题目等级划分简单题基本可采用暴力解法但是在中等及困难这两个等级暴力解法大部分都是行不通的。
解法一归并
如果要求整个数组的逆序对我们可以将数组分为两部分先求左边区域的逆序对再求右边区域的逆序对然后左边选一个、右边选一个看看这样有多少个逆序对这个的本质其实还是属于暴力枚举 我们在此想法是再优化一下即当左边区域挑选完毕之后对左区域排序右边区域挑选完毕之后对右区域排序然后再挑选一左一右挑选完毕之后再排一下序这个过程就和归并排序的过程一样了。 为什么归并会快升序为例 我们固定一个数要找出有多少个数比这个数大在上图我们看对于cur2在左区间有多少个数比这个数大这样就和归并排序完美契合分3种情况 nums[cur1] nums[cur2]–cur1和情况操作一样nums[cur1] nums[cur2] 此时cur1后面的元素全部大于nums[cur2]然后就能直接统计出一大堆ret mid - cur1 1cur2 所以这个时间复杂度就和归并排序的时间复杂度一模一样O(N*logN) 细节问题 刚刚是以升序为例如果采用降序即找出该数之后有多少个小于该数的元素 3. 代码实现
升序
class Solution {int tmp[50001];
public:int reversePairs(vectorint record){return mergeSort(record,0,record.size()-1);}int mergeSort(vectorint nums, int left, int right){if(left right) return 0;int ret 0;int mid (left right) 1;//[left,mid] [mid1,right]//左边逆序对个数 排序//右边逆序对个数 排序ret mergeSort(nums,left,mid);ret mergeSort(nums,mid1,right);//一左一右个数int cur1 left,cur2 mid1,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;}
};降序
class Solution {int tmp[50001];
public:int reversePairs(vectorint record){return mergeSort(record,0,record.size()-1);}int mergeSort(vectorint nums, int left, int right){if(left right) return 0;int ret 0;int mid (left right) 1;//[left,mid] [mid1,right]//左边逆序对个数 排序//右边逆序对个数 排序ret mergeSort(nums,left,mid);ret mergeSort(nums,mid1,right);//一左一右个数int cur1 left,cur2 mid1,i 0;while(cur1 mid cur2 right){if(nums[cur1] nums[cur2]) tmp[i] nums[cur2];else{ret right - cur2 1;tmp[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];return ret;}
};运行结果
