专业设计网站,南昌企业建站程序,网站制作服务订单,买了一个域名怎么做网站文章目录 算法原理实现思路典型例题排序数组数组中的逆序对计算右侧小于当前元素的个数 总结 算法原理
利用归并思想进行分治也是很重要的一种思路#xff0c;在解决逆序对的问题上有很大的需求空间
于是首先归并排序是首先的#xff0c;归并排序要能写出来#xff1a;
c… 文章目录 算法原理实现思路典型例题排序数组数组中的逆序对计算右侧小于当前元素的个数 总结 算法原理
利用归并思想进行分治也是很重要的一种思路在解决逆序对的问题上有很大的需求空间
于是首先归并排序是首先的归并排序要能写出来
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(leftright){return;}// 数组划分 [left,mid][mid1,right]int mid(leftright)/2;// 分块排序mergesort(nums,left,mid);mergesort(nums,mid1,right);// 合并数组int cur1left,cur2mid1,i0;while(cur1mid cur2right){if(nums[cur1]nums[cur2]){tmp[i]nums[cur1];}else{tmp[i]nums[cur2];}}while(cur1mid){tmp[i]nums[cur1];}while(cur2right){tmp[i]nums[cur2];}for(int ileft;iright;i){nums[i]tmp[i-left];}}
};以上为归并排序基本算法原理基于这个原理可以解决逆序对问题逆序对问题通常问法是给定某一个数据在整个数组中找比这个数大或者比这个数小的数统计这样的元素有多少个进而返回到数组或者直接输出
那么在找寻这个过程中这类问题的基本思路就是左边找右边找左右找
在找寻的过程中需要注意的是升序和逆序问题后续的题目中会有涉及到的地方在这里不过总结
实现思路
大体的实现思路如上总结下来就是划分为两个子区间在左边找在右边找接着左右找这样就能找到要求的结果
典型例题
排序数组 理解快速排序和归并排序思维的不同点
依旧是经典的排序数组问题这次选用归并排序来解决要了解归并排序和快速排序其实都是利用了分治的思想把一个很复杂的问题分解为一个一个的小问题二者在思维上有一些小小的区别快速排序的思想是对于某个区间来说把这个区间进行分块每一个分块都进行排序每一个都进行排序这样就完成了目的这样的思维更像是一种前序遍历完成了这次的任务后再向后进行延伸而归并排序的思路和快速排序不同归并排序的思路主要是把数组拆分成一个一个的小区间不停的拆分直到不能拆分后再进行组装它的排序过程整体上而言是滞后的更像是一种后序遍历的思想先一直向深处找直到找不下去了再进行排序再一层一层向上走
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(leftright){return;}// 数组划分 [left,mid][mid1,right]int mid(leftright)/2;// 分块排序mergesort(nums,left,mid);mergesort(nums,mid1,right);// 合并数组int cur1left,cur2mid1,i0;while(cur1mid cur2right){if(nums[cur1]nums[cur2]){tmp[i]nums[cur1];}else{tmp[i]nums[cur2];}}while(cur1mid){tmp[i]nums[cur1];}while(cur2right){tmp[i]nums[cur2];}for(int ileft;iright;i){nums[i]tmp[i-left];}}
};数组中的逆序对 利用归并排序求逆序对是解决这类问题的常见方法对于这个题来说就可以采用分治的方法来解决问题
具体来说可以把整个问题拆分为几个小步骤把当前所在区间分成两个区间在左边的区间内找符合逆序对的对数再在右边的区间内找符合逆序对的对数同时把左右两区间都进行排序这样就可以在左右区间内都寻找符合要求的逆序对数这就是一个轮回思路把整个数组拆分为一个一个小区间即可解决问题这就是分治的思想
那么思路就确认了
从左边数组中找符合要求的逆序对从右边数组中找符合要求的逆序对从左右两边数组中找符合要求的逆序对
从排列组合的分类原理来看这样就能找到所有的逆序对
从优化角度来讲第三步是可以进行优化的这就引入了要排序的原因
如何从左右两数组中找逆序对数
其实利用双指针的思想就可以解决定义cur1和cur2分别指向左右两个数组假设这里是提前排序好的升序的数组那么当cur1所指向的元素大于cur2所指的元素那么cur2所指向的元素之前的元素全部满足条件因此一次可以找出很多相同的元素这也是这个算法的原理
因此这里就引出了为什么要进行排序左右子区间排序后就可以通过上面的算法快速找到有多少满足要求的逆序对
处理剩余元素 如果是左边出现剩余说明左边剩下的所有元素都是⽐右边元素⼤的但是它们都是已经被计算过的因此不会产⽣逆序对仅需归并排序即可。 如果是右边出现剩余说明右边剩下的元素都是⽐左边⼤的不符合逆序对的定义因此也不需要处理仅需归并排序即可。
class Solution
{vectorint tmp;
public: int reversePairs(vectorint nums) {tmp.resize(50001);return mergesort(nums,0,nums.size()-1);}int mergesort(vectorint nums,int left,int right){if(leftright){return 0;}int ret0,mid(leftright)/2;retmergesort(nums,left,mid);retmergesort(nums,mid1,right);int cur1left,cur2mid1,i0;while(cur1mid cur2right){if(nums[cur1]nums[cur2]){tmp[i]nums[cur1];}else{retmid-cur11;tmp[i]nums[cur2];}}while(cur1mid){tmp[i]nums[cur1];}while(cur2right){tmp[i]nums[cur2];}for(int ileft;iright;i){nums[i]tmp[i-left];}return ret;}
};总体来说还是一道有思维量的hard题目但如果掌握了分治的思想再去下手就会容易许多
而这样的算法的时间复杂度也是很优秀的时间复杂度是O(N)
计算右侧小于当前元素的个数 有了上面的题目的思维铺垫解法还是比较好想的原理就是利用归并排序进行分治的思想
但这个题和上面的问题也有区别由于返回的是数组因此需要记录nums中每一个数组中元素在返回数组中元素的下标需要一一对应起来这是比较关键的一步也就是说每次找到符合条件的数后这个数应该被放到返回数组中的哪个位置这就需要用一个辅助数组来记录原数组中每一个元素的下标所在的位置这样就能找到了
class Solution
{vectorint ret;vectorint index;int tmpnums[500010];int tmpindex[500010];
public:vectorint countSmaller(vectorint nums) {int nnums.size();ret.resize(n);index.resize(n);for(int i0;in;i){index[i]i;}mergesort(nums,0,n-1);return ret;}void mergesort(vectorint nums,int left,int right){if(leftright){return;}int mid(leftright)/2;mergesort(nums,left,mid);mergesort(nums,mid1,right);int cur1left,cur2mid1,i0;while(cur1mid cur2right){if(nums[cur1]nums[cur2]){tmpnums[i]nums[cur2];tmpindex[i]index[cur2];}else{ret[index[cur1]]right-cur21;tmpnums[i]nums[cur1];tmpindex[i]index[cur1];}}while(cur1mid){tmpnums[i]nums[cur1];tmpindex[i]index[cur1];}while(cur2right){tmpnums[i]nums[cur2];tmpindex[i]index[cur2];}for(int jleft;jright;j){nums[j]tmpnums[j-left];index[j]tmpindex[j-left];}}
};总结
归并递归解决分治问题主要依托于归并排序在掌握归并的前提下找到归并过程中要找的关键信息
