企业官网建设流程全解析

重庆网站产品推广,php 视频网站开发,没有域名可以建网站吗,中国国家培训网官网归并排序是基于分治思想的经典排序算法#xff0c;核心逻辑是“拆分→排序→合并”#xff1a;将数组递归拆分为子数组#xff0c;分别排序后再合并为有序数组。它是稳定排序#xff08;相同元素相对位置不变#xff09;#xff0c;时间复杂度稳定为 O(nlog⁡n)O(n\log n…归并排序是基于分治思想的经典排序算法核心逻辑是“拆分→排序→合并”将数组递归拆分为子数组分别排序后再合并为有序数组。它是稳定排序相同元素相对位置不变时间复杂度稳定为O(nlog⁡n)O(n\log n)O(nlogn)不仅能解决排序问题更能高效处理“逆序对统计”“右侧元素计数”等衍生问题。本文通过4道经典题目拆解归并排序在不同场景下的解题思路与代码实现。一、排序数组题目描述实现归并排序将整数数组升序排列不能使用内置排序函数要求时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)。示例输入nums [5,2,3,1]输出[1,2,3,5]解题思路标准归并排序的三步流程拆分将数组从中间拆分为左右两个子数组递归排序子数组。合并用临时数组tmp合并两个有序子数组双指针遍历左右子数组取较小值存入临时数组。还原将临时数组的有序元素写回原数组的对应区间。完整代码classSolution{vectorinttmp;public:vectorintsortArray(vectorintnums){tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);returnnums;}voidmergeSort(vectorintnums,intleft,intright){if(leftright)return;// 1. 取中间点intmid(leftright)1;// 2. 分区间排序mergeSort(nums,left,mid);mergeSort(nums,mid1,right);// 3. 合并intcur1left,cur2mid1,i0;while(cur1midcur2right)tmp[i]nums[cur1]nums[cur2]?nums[cur1]:nums[cur2];while(cur1mid)tmp[i]nums[cur1];while(cur2right)tmp[i]nums[cur2];// 4. 还原for(intileft;iright;i){nums[i]tmp[i-left];}}};复杂度分析时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)拆分的递归深度为O(log⁡n)O(\log n)O(logn)每层合并的时间为O(n)O(n)O(n)。空间复杂度O(n)O(n)O(n)临时数组tmp存储合并结果递归栈深度为O(log⁡n)O(\log n)O(logn)可忽略。二、交易逆序对的总数经典逆序对题目描述给定股票交易记录数组record若前一天股价高于后一天股价视为一个“交易逆序对”返回逆序对总数。示例输入record [9,7,5,4,6]输出8逆序对包括(9,7)、(9,5)等解题思路在归并排序的合并阶段统计逆序对拆分并递归排序左右子数组同时统计子数组内部的逆序对。合并时若左子数组的当前元素nums[cur1] nums[cur2]说明左子数组中cur1~mid的所有元素都与nums[cur2]构成逆序对逆序对数量增加mid - cur1 1。合并完成后将有序元素写回原数组。完整代码classSolution{vectorinttmp;public:intreversePairs(vectorintrecord){tmp.resize(record.size());returnmergeSort(record,0,record.size()-1);}intmergeSort(vectorintnums,intleft,intright){if(leftright)return0;intret0;// 1. 找中点划分区间intmid(leftright)1;// 2. 找左/右区间个数并排序retmergeSort(nums,left,mid);retmergeSort(nums,mid1,right);inti0,cur1left,cur2mid1;// 3. 一左一右找并合并排序while(cur1midcur2right){if(nums[cur1]nums[cur2])tmp[i]nums[cur1];else{retmid-cur11;tmp[i]nums[cur2];}}// 4. 处理剩余元素while(cur1mid)tmp[i]nums[cur1];while(cur2right)tmp[i]nums[cur2];// 5. 还原for(intileft;iright;i)nums[i]tmp[i-left];returnret;}};复杂度分析时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)排序与统计逆序对的时间均为O(nlog⁡n)O(n\log n)O(nlogn)。空间复杂度O(n)O(n)O(n)临时数组tmp存储合并结果。三、计算右侧小于当前元素的个数带索引的逆序统计题目描述返回数组counts其中counts[i]是nums[i]右侧小于nums[i]的元素数量。示例输入nums [5,2,6,1]输出[2,1,1,0]解题思路在归并排序中维护元素的原始索引从而统计每个元素右侧更小的元素数量用index数组记录元素的原始索引合并时同步维护索引的顺序。合并阶段若左子数组的当前元素nums[cur1] nums[cur2]说明nums[cur1]右侧存在right - cur2 1个更小的元素将该值累加到ret[index[cur1]]。合并完成后同步还原nums和index数组的顺序。完整代码classSolution{vectorintret;vectorintindex;inttmpNums[500010];inttmpIndex[500010];public:vectorintcountSmaller(vectorintnums){intnnums.size();ret.resize(n);index.resize(n);for(inti0;in;i)index[i]i;mergeSort(nums,0,n-1);returnret;}voidmergeSort(vectorintnums,intleft,intright){if(leftright)return;intmid(leftright)1;mergeSort(nums,left,mid);mergeSort(nums,mid1,right);intcur1left,cur2mid1,i0;while(cur1midcur2right){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(intileft;iright;i){nums[i]tmpNums[i-left];index[i]tmpIndex[i-left];}}};复杂度分析时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)排序与统计的时间均为O(nlog⁡n)O(n\log n)O(nlogn)。空间复杂度O(n)O(n)O(n)存储临时数组和索引数组。四、翻转对扩展逆序对题目描述若i j且nums[i] 2 * nums[j]则称(i,j)为“翻转对”返回数组中的翻转对总数。示例输入nums [1,3,2,3,1]输出2翻转对为(3,1)、(3,1)解题思路在归并排序的合并前阶段统计翻转对拆分并递归排序左右子数组同时统计子数组内部的翻转对。合并前用双指针遍历左右子数组若nums[cur1] 2 * nums[cur2]则左子数组中cur1~mid的所有元素都与nums[cur2]构成翻转对翻转对数量增加mid - cur1 1并右移cur2否则右移cur1。统计完成后合并两个有序子数组并写回原数组。完整代码classSolution{inttmp[50010];public:intreversePairs(vectorintnums){returnmergeSort(nums,0,nums.size()-1);}intmergeSort(vectorintnums,intleft,intright){if(leftright)return0;intret0;intmid(leftright)1;retmergeSort(nums,left,mid);retmergeSort(nums,mid1,right);// 合并前统计翻转对intcur1left,cur2mid1;while(cur1mid){while(cur2rightnums[cur1]/2.0nums[cur2])cur2;if(cur2right)break;retright-cur21;cur1;}// 合并两个有序子数组cur1left,cur2mid1;inti0;while(cur1midcur2right)tmp[i]nums[cur1]nums[cur2]?nums[cur2]:nums[cur1];while(cur1mid)tmp[i]nums[cur1];while(cur2right)tmp[i]nums[cur2];for(intileft;iright;i)nums[i]tmp[i-left];returnret;}};复杂度分析时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)统计翻转对与合并的时间均为O(nlog⁡n)O(n\log n)O(nlogn)。空间复杂度O(n)O(n)O(n)临时数组tmp存储合并结果。