淮安网站建设案例,网站后台文章编辑器,外贸网站建设 soho,百度收录好的网站文章目录 分治专题#xff08;二#xff09;#xff1a;归并排序的核心思想与进阶应用前言、第二章#xff1a;归并排序的应用与延展2.1 归并排序#xff08;medium#xff09;解法#xff08;归并排序#xff09;C 代码实现易错点提示时间复杂度和空间复杂度 2.2 数组… 文章目录 分治专题二归并排序的核心思想与进阶应用前言、第二章归并排序的应用与延展2.1 归并排序medium解法归并排序C 代码实现易错点提示时间复杂度和空间复杂度 2.2 数组中的逆序对hard解法利用归并排序的过程 — 分治核心步骤与实现细节C 代码实现易错点提示时间复杂度和空间复杂度 2.3 计算右侧小于当前元素的个数hard解法利用归并排序的过程 — 分治核心步骤C 代码实现易错点提示时间复杂度和空间复杂度 2.4 翻转对hard解法归并排序 — 分治核心步骤与实现细节C 代码实现易错点提示时间复杂度和空间复杂度优化点 写在最后 分治专题二归并排序的核心思想与进阶应用 欢迎讨论如果您对内容有任何疑问或见解欢迎在评论区留言。 点赞、收藏与分享如果觉得这篇文章对您有帮助请点赞、收藏并分享给更多朋友。 分享给更多人一起学习分治策略掌握归并排序的精髓 前言、
上篇【优选算法篇】化繁为简见素抱朴从乱象中重构秩序的艺术 归并排序是经典的分治法应用其核心在于“分而治之”的思想。通过不断划分将一个复杂问题逐步拆解成若干规模更小的子问题以递归方式求解再将解合并从而解决初始问题。本文将围绕归并排序的基本原理结合排序数组的题目深入剖析归并排序在分治中的实际应用。 第二章归并排序的应用与延展
2.1 归并排序medium
题目链接912. 排序数组
题目描述
给定一个整数数组 nums请将该数组按升序排列。
示例 1
输入nums [5,2,3,1]输出[1,2,3,5]
示例 2
输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5] 解法归并排序
算法思路
归并排序的过程充分体现了“分而治之”的思想基本步骤分为以下两部分 分将数组一分为二递归地继续分割直到每个子数组的长度为 1确保所有分块都已排序。 治将两个已排序的子数组合并成一个有序数组最终返回整个数组的有序结果。
具体步骤
使用中间点将数组分成 [left, mid] 和 [mid 1, right] 两部分。递归对左右区间进行排序。在排序好的左右子数组中使用双指针将较小的元素依次合并到临时数组 tmp 中。合并完成后将 tmp 数组的内容拷贝回原数组。 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 (left right) return; // 递归终止条件// 1. 分区int mid (left right) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid 1, right);// 2. 合并两个已排序数组int cur1 left, cur2 mid 1, i 0;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]; // 右边剩余部分// 3. 拷贝回原数组for (int j 0; j i; j) {nums[left j] tmp[j];}}
};易错点提示 递归终止条件 在 mergeSort 函数中left right 时停止递归以防止无穷递归导致的栈溢出。 合并逻辑 cur1 和 cur2 分别指向左、右子数组的起始位置使用 tmp 存储合并结果。确保在所有元素都合并后将 tmp 拷贝回 nums 中。 临时数组的使用 临时数组 tmp 存储每一轮合并结果以确保排序结果被完整保留到下一轮递归。 时间复杂度和空间复杂度
时间复杂度O(n log n)。每轮合并的时间复杂度为 O(n)分区深度为 log n。空间复杂度O(n)临时数组 tmp 占用额外空间。 2.2 数组中的逆序对hard
题目链接剑指 Offer 51. 数组中的逆序对
题目描述
在一个数组中的两个数字如果前面的一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数。
示例 1
输入[7,5,6,4]输出5 解法利用归并排序的过程 — 分治
算法思路
归并排序求逆序数是经典的方法。在归并排序的合并过程中我们可以顺便统计出逆序对的数量这样可以避免暴力统计的 O(n^2) 时间复杂度。
逆序对的产生方式可分为三种情况
左数组中的元素逆序。右数组中的元素逆序。左数组和右数组中的元素形成逆序。
归并排序过程可以分为两个步骤
分将数组一分为二不断划分直到每个子数组长度为1。治将左右子数组合并成一个有序数组的过程中统计逆序对的数量。 核心步骤与实现细节 为什么可以利用归并排序求逆序对 因为在归并排序的过程中我们通过分治的方法将数组拆分成左右两部分。每部分内部的逆序对可以分别在排序的过程中统计。最终在归并左右数组时可以统计那些横跨左右数组的逆序对这三者相加即为总的逆序对数。 核心问题如何在合并两个有序数组的过程中统计逆序对的数量 在合并左右两个已排序的数组时可以高效统计出横跨两个数组的逆序对数。考虑以下例子 假设有两个有序序列 left [5, 7, 9] 和 right [4, 5, 8]。 目标是计算在合并的过程中 left 中的元素大于 right 中的元素的情况数量。 合并并统计逆序对的过程 定义指针 cur1 遍历 left 数组cur2 遍历 right 数组。 定义 ret 记录逆序对的数量help 数组临时存储排序的结果。 第一轮 比较 left[cur1] 和 right[cur2]如果 left[cur1] right[cur2]则意味着从 cur1 到末尾的元素都大于 right[cur2]因为 left 是有序的。我们可以确定逆序对数量并将结果累加到 ret。若 left[cur1] right[cur2]则将 left[cur1] 添加到 help 数组中。 处理剩余元素若一侧数组元素遍历完剩余元素直接添加到 help 数组即可不会再产生新的逆序对。 C 代码实现
class Solution {int tmp[50010]; // 临时数组
public:int reversePairs(vectorint nums) {return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vectorint nums, int left, int right) {if (left right) return 0; // 递归终止条件int ret 0;// 1. 找中间点将数组分成两部分int mid (left right) 1;// 2. 左、右部分的逆序对数量ret mergeSort(nums, left, mid);ret mergeSort(nums, mid 1, right);// 3. 合并并统计逆序对数量int cur1 left, cur2 mid 1, 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];}}// 4. 处理剩余元素while (cur1 mid) tmp[i] nums[cur1];while (cur2 right) tmp[i] nums[cur2];// 5. 将 tmp 数组内容拷贝回原数组for (int j left; j right; j) {nums[j] tmp[j - left];}return ret;}
};易错点提示 递归终止条件 当 left right 时表示已将数组分割到单个元素递归停止返回0。 统计逆序对 当 nums[cur1] nums[cur2] 时说明 left[cur1] 及后面的所有元素都大于 right[cur2]则这些元素与 right[cur2] 构成逆序对。统计并更新 ret 的值。 处理剩余元素 若左数组或右数组有剩余则直接将剩余部分加入到 tmp因为剩余部分不会形成逆序对。 拷贝回原数组 最后将 tmp 的排序结果拷贝回 nums确保在递归的上一级合并时数组依旧有序。 时间复杂度和空间复杂度
时间复杂度O(n log n)。归并排序的分治递归实现使得时间复杂度达到 O(n log n)。空间复杂度O(n)需要额外的数组存储合并结果。 2.3 计算右侧小于当前元素的个数hard
题目链接315. 计算右侧小于当前元素的个数
题目描述
给你一个整数数组 nums 按要求返回一个新数组 counts。 数组 counts 有如下性质counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1
输入nums [5,2,6,1]输出[2,1,1,0]
解释
5 的右侧有 2 个更小的元素2 和 1。2 的右侧有 1 个更小的元素1。6 的右侧有 1 个更小的元素1。1 的右侧有 0 个更小的元素。 解法利用归并排序的过程 — 分治
算法思路
本题和求数组中的逆序对非常类似但与逆序对的统计不同之处在于
需要返回一个数组 counts记录每个元素右侧更小的元素数量而不是单一的逆序对总数。归并排序过程中除了排序还需要记录排序过程中元素的索引位置的变化。 核心步骤 辅助数组和索引绑定 定义一个 index 数组用于记录元素对应的原始索引确保元素与下标绑定在一起。ret 数组存储每个元素右侧更小元素的数量。 递归排序 递归地对数组进行分治排序并统计左右子数组中每个元素右侧更小的元素数量。 合并排序并统计逆序对 当合并两个有序数组时如果发现左侧的某个元素大于右侧的当前元素则说明该左侧元素右侧的所有元素都小于它。将这些逆序对数量累加到对应的 ret 索引上。同时完成左右子数组的归并操作。 C 代码实现
class Solution {vectorint ret; // 结果数组vectorint index; // 记录元素的原始下标int tmpNums[100010]; // 临时数组用于排序int tmpIndex[100010]; // 临时数组用于记录索引排序public:vectorint countSmaller(vectorint nums) {int n nums.size();ret.resize(n, 0); // 初始化结果数组为0index.resize(n); // 初始化下标数组for (int i 0; i n; i) {index[i] i; // 初始时索引与数组位置一一对应}mergeSort(nums, 0, n - 1);return ret;}void mergeSort(vectorint nums, int left, int right) {if (left right) return;// 1. 分区int mid (left right) / 2;// 2. 递归处理左右子区间mergeSort(nums, left, mid);mergeSort(nums, mid 1, right);// 3. 合并并统计逆序对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 j left; j right; j) {nums[j] tmpNums[j - left];index[j] tmpIndex[j - left];}}
};易错点提示 确保索引正确绑定 在每次合并的过程中索引数组 index 也需要同步排序以保证结果数组 ret 的统计准确。 统计逆序对的逻辑 当 nums[cur1] nums[cur2] 时说明从 cur2 到 right 的所有元素都小于 nums[cur1]需要将这些数量累加到 ret[index[cur1]]。 递归终止条件 当 left right 时停止递归避免无效操作。 时间复杂度和空间复杂度
时间复杂度O(n log n)。分治递归的时间复杂度是 O(log n)每次合并的时间复杂度是 O(n)。空间复杂度O(n)。需要额外的临时数组 tmpNums 和 tmpIndex 进行合并排序。 2.4 翻转对hard
题目链接493. 翻转对
题目描述
给定一个数组 nums如果 i j 且 nums[i] 2 * nums[j]我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。
示例 1
输入nums [1,3,2,3,1]输出2 解法归并排序 — 分治
算法思路
翻转对的统计与逆序对非常类似都可以利用 归并排序 的思想将问题分解为三部分
左数组中的翻转对数量。右数组中的翻转对数量。左右数组合并时的翻转对数量。
由于翻转对要求的是 nums[i] 2 * nums[j]直接在合并排序时统计会比较困难因此
我们在归并排序前提前统计 左右两部分数组中满足条件的翻转对数量。在统计完成后再进行归并排序。 核心步骤与实现细节 统计翻转对数量 使用两个指针 cur1 和 cur2分别遍历左、右子数组。对于每个左数组元素 nums[cur1]找到右数组中第一个不满足 nums[cur1] 2 * nums[cur2] 的位置 cur2。此时cur2 - mid - 1 即为当前 cur1 的翻转对数量累加到结果中。 合并两个有序数组 合并时按照归并排序的逻辑将两个子数组排序并写入临时数组。 递归分治 每次划分数组为 [left, mid] 和 [mid 1, right]递归统计翻转对数量并排序。 C 代码实现
class Solution {int tmp[50010]; // 临时数组用于合并排序
public:int reversePairs(vectorint nums) {return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vectorint nums, int left, int right) {if (left right) return 0;int ret 0;// 1. 分区int mid (left right) / 2;// 2. 递归计算左右区间的翻转对数量ret mergeSort(nums, left, mid);ret mergeSort(nums, mid 1, right);// 3. 统计翻转对数量int cur1 left, cur2 mid 1;while (cur1 mid) {while (cur2 right nums[cur2] * 2 nums[cur1]) {cur2;}ret cur2 - mid - 1;cur1;}// 4. 合并两个有序数组cur1 left, cur2 mid 1;int i left;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 j left; j right; j) {nums[j] tmp[j];}return ret;}
};易错点提示 统计翻转对的逻辑 必须确保 cur2 指针只向右移动不会回退避免重复计算。注意翻转对的判断条件 nums[cur1] 2 * nums[cur2]需要考虑到浮点运算可能导致的精度问题因此 2 * nums[cur2] 可能需要写成 nums[cur1] 2LL * nums[cur2]。 归并排序的逻辑 合并时确保临时数组和原数组的元素同步避免在递归的上一层出错。 边界条件 单元素或空数组的递归终止条件是 left right。 时间复杂度和空间复杂度 时间复杂度O(n log n)。 每次递归的深度是 log n每层递归需要合并排序和统计翻转对复杂度为 O(n)。 空间复杂度O(n)。 使用了额外的临时数组 tmp 进行排序。 优化点
使用更大的临时数组避免频繁分配内存。在统计翻转对时提前检查是否有可能的翻转对减少无意义的遍历。
通过以上方法翻转对的数量可以在 O(n log n) 的时间复杂度内高效统计。
写在最后 在本次归并排序专题中我们以经典的分治思想为核心逐层剖析了归并排序的精髓及其在算法中的高级应用。从数组排序到统计逆序对再到复杂的翻转对和右侧更小元素计数归并排序不仅是解决基础问题的利器更是攻克高阶难题的关键。我们以逐步深入的方式从基础实现到优化分析贯穿了分治思想的深度与广度。 分治法的核心在于“分而治之”通过不断将大问题拆解为小问题并利用递归与合并的方式重新组合结果。在归并排序中借助临时数组和指针操作我们能够高效完成排序并在此过程中完成复杂的统计任务。它不仅展现了算法的美学更体现了计算机科学中化繁为简的哲学。 通过归并排序的深入学习我们不仅掌握了分治策略的实现更体验了算法优化的艺术。期待这篇文章能为读者打开分治法的大门让你在算法学习中游刃有余 以上就是关于【优选算法篇】分治乾坤万物归一在重组中窥见无声的秩序的内容啦各位大佬有什么问题欢迎在评论区指正或者私信我也是可以的啦您的支持是我创作的最大动力❤️
文章转载自： http://www.morning.tktcr.cn.gov.cn.tktcr.cn http://www.morning.znkls.cn.gov.cn.znkls.cn http://www.morning.wnjrf.cn.gov.cn.wnjrf.cn http://www.morning.fdzzh.cn.gov.cn.fdzzh.cn http://www.morning.lpbrp.cn.gov.cn.lpbrp.cn http://www.morning.ggtgl.cn.gov.cn.ggtgl.cn http://www.morning.yqmmh.cn.gov.cn.yqmmh.cn http://www.morning.cbchz.cn.gov.cn.cbchz.cn http://www.morning.qxkcx.cn.gov.cn.qxkcx.cn http://www.morning.yfcyh.cn.gov.cn.yfcyh.cn http://www.morning.wfcqr.cn.gov.cn.wfcqr.cn http://www.morning.wttzp.cn.gov.cn.wttzp.cn http://www.morning.gzxnj.cn.gov.cn.gzxnj.cn http://www.morning.vtbtje.cn.gov.cn.vtbtje.cn http://www.morning.kpcky.cn.gov.cn.kpcky.cn http://www.morning.ykwgl.cn.gov.cn.ykwgl.cn http://www.morning.kfmnf.cn.gov.cn.kfmnf.cn http://www.morning.qptbn.cn.gov.cn.qptbn.cn http://www.morning.bfkrf.cn.gov.cn.bfkrf.cn http://www.morning.jtybl.cn.gov.cn.jtybl.cn http://www.morning.nqmdc.cn.gov.cn.nqmdc.cn http://www.morning.jltmb.cn.gov.cn.jltmb.cn http://www.morning.mdrnn.cn.gov.cn.mdrnn.cn http://www.morning.flxgx.cn.gov.cn.flxgx.cn http://www.morning.qgmbx.cn.gov.cn.qgmbx.cn http://www.morning.dnqpq.cn.gov.cn.dnqpq.cn http://www.morning.kbyp.cn.gov.cn.kbyp.cn http://www.morning.sqnrz.cn.gov.cn.sqnrz.cn http://www.morning.nuobeiergw.cn.gov.cn.nuobeiergw.cn http://www.morning.schwr.cn.gov.cn.schwr.cn http://www.morning.hrqfl.cn.gov.cn.hrqfl.cn http://www.morning.zgdnz.cn.gov.cn.zgdnz.cn http://www.morning.nndbz.cn.gov.cn.nndbz.cn http://www.morning.grbp.cn.gov.cn.grbp.cn http://www.morning.nkkr.cn.gov.cn.nkkr.cn http://www.morning.rybr.cn.gov.cn.rybr.cn http://www.morning.brqjs.cn.gov.cn.brqjs.cn http://www.morning.brmbm.cn.gov.cn.brmbm.cn http://www.morning.xflwq.cn.gov.cn.xflwq.cn http://www.morning.jbztm.cn.gov.cn.jbztm.cn http://www.morning.tfrlj.cn.gov.cn.tfrlj.cn http://www.morning.ysbrz.cn.gov.cn.ysbrz.cn http://www.morning.wkmyt.cn.gov.cn.wkmyt.cn http://www.morning.yqsq.cn.gov.cn.yqsq.cn http://www.morning.wchsx.cn.gov.cn.wchsx.cn http://www.morning.rqfnl.cn.gov.cn.rqfnl.cn http://www.morning.ytfr.cn.gov.cn.ytfr.cn http://www.morning.yxwcj.cn.gov.cn.yxwcj.cn http://www.morning.zhghd.cn.gov.cn.zhghd.cn http://www.morning.ypnxq.cn.gov.cn.ypnxq.cn http://www.morning.kqpsj.cn.gov.cn.kqpsj.cn http://www.morning.crkmm.cn.gov.cn.crkmm.cn http://www.morning.bqppr.cn.gov.cn.bqppr.cn http://www.morning.zrpys.cn.gov.cn.zrpys.cn http://www.morning.nqlx.cn.gov.cn.nqlx.cn http://www.morning.qhkx.cn.gov.cn.qhkx.cn http://www.morning.jcwhk.cn.gov.cn.jcwhk.cn http://www.morning.sflnx.cn.gov.cn.sflnx.cn http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.krkwh.cn.gov.cn.krkwh.cn http://www.morning.ljdjn.cn.gov.cn.ljdjn.cn http://www.morning.mgkb.cn.gov.cn.mgkb.cn http://www.morning.rgfx.cn.gov.cn.rgfx.cn http://www.morning.flfxb.cn.gov.cn.flfxb.cn http://www.morning.rythy.cn.gov.cn.rythy.cn http://www.morning.qbwyd.cn.gov.cn.qbwyd.cn http://www.morning.sbczr.cn.gov.cn.sbczr.cn http://www.morning.qgzmz.cn.gov.cn.qgzmz.cn http://www.morning.wdlyt.cn.gov.cn.wdlyt.cn http://www.morning.wkws.cn.gov.cn.wkws.cn http://www.morning.qftzk.cn.gov.cn.qftzk.cn http://www.morning.jjzrh.cn.gov.cn.jjzrh.cn http://www.morning.ynlbj.cn.gov.cn.ynlbj.cn http://www.morning.yrhsg.cn.gov.cn.yrhsg.cn http://www.morning.ptwqf.cn.gov.cn.ptwqf.cn http://www.morning.rqhn.cn.gov.cn.rqhn.cn http://www.morning.newfeiya.com.cn.gov.cn.newfeiya.com.cn http://www.morning.dmlgq.cn.gov.cn.dmlgq.cn http://www.morning.wpsfc.cn.gov.cn.wpsfc.cn http://www.morning.lbcfj.cn.gov.cn.lbcfj.cn
