空间复杂度：O(n)

发布时间：2025-06-24 18:24:56 作者：北方职教升学中心阅读量：228

2.3 计算右侧小于当前元素的个数（hard）

题目链接：315. 计算右侧小于当前元素的个数

题目描述：

给你一个整数数组 nums，按要求返回一个新数组 counts。

空间复杂度：O(n)。它不仅展现了算法的美学，更体现了计算机科学中化繁为简的哲学。

逆序对的产生方式可分为三种情况：

左数组中的元素逆序。
递归排序：
- 递归地对数组进行分治排序，并统计左右子数组中每个元素右侧更小的元素数量。
  数组 counts有如下性质：counts[i]的值是 nums[i]右侧小于 nums[i]的元素的数量。
临时数组的使用：
- 临时数组 tmp存储每一轮合并结果，以确保排序结果被完整保留到下一轮递归。
  👍 点赞、
- 若 left[cur1] <= right[cur2]，则将 left[cur1]添加到 help数组中。
递归终止条件：
- 当 left >= right时停止递归，避免无效操作。

C++ 代码实现

classSolution{vector<int>ret;// 结果数组vector<int>index;// 记录元素的原始下标inttmpNums[100010];// 临时数组用于排序inttmpIndex[100010];// 临时数组用于记录索引排序public:vector<int>countSmaller(vector<int>&nums){intn =nums.size();ret.resize(n,0);// 初始化结果数组为0index.resize(n);// 初始化下标数组for(inti =0;i <n;i++){index[i]=i;// 初始时，索引与数组位置一一对应}mergeSort(nums,0,n -1);returnret;}voidmergeSort(vector<int>&nums,intleft,intright){if(left >=right)return;// 1. 分区intmid =(left +right)/2;// 2. 递归处理左右子区间mergeSort(nums,left,mid);mergeSort(nums,mid +1,right);// 3. 合并并统计逆序对intcur1 =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(intj =left;j <=right;j++){nums[j]=tmpNums[j -left];index[j]=tmpIndex[j -left];}}};

易错点提示

确保索引正确绑定：
- 在每次合并的过程中，索引数组 index也需要同步排序，以保证结果数组 ret的统计准确。收藏与分享：如果觉得这篇文章对您有帮助，请点赞、通过不断划分，将一个复杂问题逐步拆解成若干规模更小的子问题，以递归方式求解，再将解合并，从而解决初始问题。

归并排序过程可以分为两个步骤：

分：将数组一分为二，不断划分，直到每个子数组长度为1。
左右数组合并时的翻转对数量。
空间复杂度：O(n)，临时数组 tmp占用额外空间。期待这篇文章能为读者打开分治法的大门，让你在算法学习中游刃有余！
以上就是关于【优选算法篇】分治乾坤，万物归一：在重组中窥见无声的秩序的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

C++ 代码实现

classSolution{vector<int>tmp;// 临时数组用于存储合并结果public:vector<int>sortArray(vector<int>&nums){tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);returnnums;}// 归并排序voidmergeSort(vector<int>&nums,intleft,intright){if(left >=right)return;// 递归终止条件// 1. 分区intmid =(left +right)/2;mergeSort(nums,left,mid);mergeSort(nums,mid +1,right);// 2. 合并两个已排序数组intcur1 =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(intj =0;j <i;++j){nums[left +j]=tmp[j];}}};

易错点提示

递归终止条件：
- 在 mergeSort函数中，left >= right时停止递归，以防止无穷递归导致的栈溢出。
- 在排序好的左右子数组中，使用双指针将较小的元素依次合并到临时数组 tmp中。

具体步骤：

使用中间点将数组分成 [left, mid]和 [mid + 1, right]两部分。

合并排序并统计逆序对：

当合并两个有序数组时，如果发现左侧的某个元素大于右侧的当前元素，则说明该左侧元素右侧的所有元素都小于它。

2.2 数组中的逆序对（hard）

题目链接：剑指 Offer 51. 数组中的逆序对

题目描述：

在一个数组中的两个数字，如果前面的一个数字大于后面的数字，则这两个数字组成一个逆序对。

核心步骤与实现细节

统计翻转对数量：
- 使用两个指针 cur1和 cur2，分别遍历左、
  示例 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. 分：将数组一分为二，递归地继续分割，直到每个子数组的长度为 1，确保所有分块都已排序。
  2. 1 的右侧有 0 个更小的元素。
拷贝回原数组：
- 最后将 tmp的排序结果拷贝回 nums，确保在递归的上一级合并时数组依旧有序。将这些逆序对数量累加到对应的 ret索引上。
2.4 翻转对（hard）
题目链接：493. 翻转对
题目描述：
给定一个数组 nums，如果 i < j且 nums[i] > 2 * nums[j]，我们就将 (i, j)称作一个重要翻转对。右部分的逆序对数量ret +=mergeSort(nums,left,mid);ret +=mergeSort(nums,mid +1,right);// 3. 合并并统计逆序对数量intcur1 =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(intj =left;j <=right;j++){nums[j]=tmp[j -left];}returnret;}};
易错点提示
1. 递归终止条件：
  - 当 left >= right时，表示已将数组分割到单个元素，递归停止返回0。
  - 核心问题：如何在合并两个有序数组的过程中统计逆序对的数量？
    在合并左右两个已排序的数组时，可以高效统计出横跨两个数组的逆序对数。需要额外的临时数组 tmpNums和 tmpIndex进行合并排序。
  - 在统计完成后，再进行归并排序。
    文章目录
    分治专题（二）：归并排序的核心思想与进阶应用
    前言、收藏并分享给更多朋友。
    解法（利用归并排序的过程 — 分治）
    算法思路：
    本题和求数组中的逆序对非常类似，但与逆序对的统计不同之处在于：
    需要返回一个数组 counts，记录每个元素右侧更小的元素数量，而不是单一的逆序对总数。
    治：将左右子数组合并成一个有序数组的过程中，统计逆序对的数量。
    合并逻辑：
    cur1和 cur2分别指向左、本文将围绕归并排序的基本原理，结合排序数组的题目，深入剖析归并排序在分治中的实际应用。
    6 的右侧有 1 个更小的元素（1）。每部分内部的逆序对可以分别在排序的过程中统计。
    分治法的核心在于“分而治之”，通过不断将大问题拆解为小问题，并利用递归与合并的方式重新组合结果。
    每次递归的深度是 log n，每层递归需要合并排序和统计翻转对，复杂度为 O(n)。
    2 的右侧有 1 个更小的元素（1）。从数组排序到统计逆序对，再到复杂的翻转对和右侧更小元素计数，归并排序不仅是解决基础问题的利器，更是攻克高阶难题的关键。每轮合并的时间复杂度为 O(n)，分区深度为 log n。
    示例 1：
    输入：nums = [5,2,6,1]
    输出：[2,1,1,0]
    解释：
    5 的右侧有 2 个更小的元素（2 和 1）。
    目标是计算在合并的过程中 left中的元素大于 right中的元素的情况数量。确保在所有元素都合并后，将 tmp拷贝回 nums中。最终在归并左右数组时，可以统计那些横跨左右数组的逆序对，这三者相加即为总的逆序对数。
    定义 ret记录逆序对的数量，help数组临时存储排序的结果。
    第二章：归并排序的应用与延展
    2.1 归并排序（medium）
    题目链接：912. 排序数组
    题目描述：
    给定一个整数数组 nums，请将该数组按升序排列。
    处理剩余元素：若一侧数组元素遍历完，剩余元素直接添加到 help数组即可，不会再产生新的逆序对。
    同时，完成左右子数组的归并操作。
    上篇：【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术
    归并排序是经典的分治法应用，其核心在于“分而治之”的思想。
  - 统计逆序对：
    - 当 nums[cur1] > nums[cur2]时，说明 left[cur1]及后面的所有元素都大于 right[cur2]，则这些元素与 right[cur2]构成逆序对。
    - 合并并统计逆序对的过程：
      定义指针 cur1遍历 left数组，cur2遍历 right数组。
  - 递归分治：
    - 每次划分数组为 [left, mid]和 [mid + 1, right]，递归统计翻转对数量并排序。我们以逐步深入的方式，从基础实现到优化分析，贯穿了分治思想的深度与广度。
  - 统计逆序对的逻辑：
    - 当 nums[cur1] > nums[cur2]时，说明从 cur2到 right的所有元素都小于 nums[cur1]，需要将这些数量累加到 ret[index[cur1]]。
  - 边界条件：
    - 单元素或空数组的递归终止条件是 left >= right。
时间复杂度和空间复杂度
- 时间复杂度：O(n log n)。

时间复杂度和空间复杂度

时间复杂度：O(n log n)。
此时，cur2 - mid - 1即为当前 cur1的翻转对数量，累加到结果中。

核心步骤

辅助数组和索引绑定：
- 定义一个 index数组，用于记录元素对应的原始索引，确保元素与下标绑定在一起。我们可以确定逆序对数量并将结果累加到 ret。
处理剩余元素：
- 若左数组或右数组有剩余，则直接将剩余部分加入到 tmp，因为剩余部分不会形成逆序对。
  写在最后
  在本次归并排序专题中，我们以经典的分治思想为核心，逐层剖析了归并排序的精髓及其在算法中的高级应用。

时间复杂度和空间复杂度

时间复杂度：O(n log n)。
合并完成后，将 tmp数组的内容拷贝回原数组。
- 使用了额外的临时数组 tmp进行排序。
- 治：将两个已排序的子数组合并成一个有序数组，最终返回整个数组的有序结果。
  示例 1：
  - 输入：nums = [1,3,2,3,1]
  - 输出：2
  解法（归并排序 — 分治）
  算法思路：
  翻转对的统计与逆序对非常类似，都可以利用 归并排序的思想，将问题分解为三部分：
  1. 左数组中的翻转对数量。
  2. 在统计翻转对时，提前检查是否有可能的翻转对，减少无意义的遍历。
  3. ret数组存储每个元素右侧更小元素的数量。
    你需要返回给定数组中的重要翻转对的数量。
  4. 右数组中的元素逆序。
  通过以上方法，翻转对的数量可以在 O(n log n)的时间复杂度内高效统计。
合并两个有序数组：
- 合并时，按照归并排序的逻辑，将两个子数组排序，并写入临时数组。
归并排序的逻辑：
- 合并时，确保临时数组和原数组的元素同步，避免在递归的上一层出错。
- 左数组和右数组中的元素形成逆序。
- 对于每个左数组元素 nums[cur1]，找到右数组中第一个不满足 nums[cur1] > 2 * nums[cur2]的位置 cur2。
- 第二章：归并排序的应用与延展
- - 2.1 归并排序（medium）
  - - 解法（归并排序）
    - C++ 代码实现
    - 易错点提示
    - 时间复杂度和空间复杂度
  - 2.2 数组中的逆序对（hard）
  - - 解法（利用归并排序的过程 — 分治）
    - 核心步骤与实现细节
    - C++ 代码实现
    - 易错点提示
    - 时间复杂度和空间复杂度
  - 2.3 计算右侧小于当前元素的个数（hard）
  - - 解法（利用归并排序的过程 — 分治）
    - 核心步骤
    - C++ 代码实现
    - 易错点提示
    - 时间复杂度和空间复杂度
  - 2.4 翻转对（hard）
  - - 解法（归并排序 — 分治）
    - 核心步骤与实现细节
    - C++ 代码实现
    - 易错点提示
    - 时间复杂度和空间复杂度
    - 优化点
- 写在最后

学生姓名：
男女
联系电话：
意向班型：
我是学生我是家长

咨询热线：	400-029-7969
咨询电话：	029-61855169 029-61855069
学校邮箱：	bfzx365@163.com
学校地址：	西安市雁塔区长安西路66号

空间复杂度：O(n)

2.3 计算右侧小于当前元素的个数（hard）

C++ 代码实现

易错点提示

C++ 代码实现

易错点提示

2.2 数组中的逆序对（hard）

核心步骤与实现细节

解法（归并排序）

2.4 翻转对（hard）

易错点提示

文章目录

解法（利用归并排序的过程 — 分治）

第二章：归并排序的应用与延展

2.1 归并排序（medium）

时间复杂度和空间复杂度

时间复杂度和空间复杂度

核心步骤

写在最后

时间复杂度和空间复杂度

解法（归并排序 — 分治）

分治专题（二）：归并排序的核心思想与进阶应用

C++ 代码实现

核心步骤与实现细节

时间复杂度和空间复杂度

C++ 代码实现

易错点提示

优化点

解法（利用归并排序的过程 — 分治）