目录一、归并排序的基本思想二、合并两个有序区间1. 为什么需要辅助数组2. 为什么复制时使用 j - left三、普通归并排序的 Java 代码复杂度四、题目一排序数组五、题目二数组中的逆序对六、题目三计算右侧小于当前元素的个数七、题目四翻转对八、4 道题共同形成的归并排序规律规律一所有题都可以拆成“左边、右边、合并”规律二区间有序后可以一次统计一整段规律三需要返回原始位置时数字必须和下标绑定规律四普通归并和特殊统计要分清先后九、常见 Java 写法创建辅助数组获取数组长度创建整数列表三目运算符十、这一阶段的总结归并排序最有价值的地方不只是把数组排好序而是可以利用“左右两部分已经有序”这一条件在合并过程中顺便统计很多信息。这篇文章从 4 道题开始普通排序、数组中的逆序对、计算右侧小于当前元素的个数以及翻转对。前 3 道题逐步增加难度最后一题会展示如何在归并之前使用双指针统计特殊的大小关系。本文涉及的题目链接912排序数组剑指 Offer 51数组中的逆序对315计算右侧小于当前元素的个数493翻转对一、归并排序的基本思想归并排序体现的是“先拆开再合并”的过程。对于数组区间[left, right]找到中间位置mid把区间拆成[left, mid]和[mid 1, right]递归处理左半部分递归处理右半部分将两个已经有序的部分合并起来。一直拆到区间中只剩一个元素。一个元素天然是有序的然后再从小区间开始逐步合并最终得到完整的有序数组。归并排序的固定结构是if(left right) return; int mid (left right) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); // 合并两个有序区间二、合并两个有序区间假设左半部分和右半部分已经分别有序左半部分[1, 5, 8] 右半部分[2, 4, 9]使用两个指针cur1指向左半部分当前要比较的位置cur2指向右半部分当前要比较的位置。比较两个指针指向的数字谁小就把谁放入辅助数组tmp并移动对应指针。int cur1 left; int cur2 mid 1; int i 0;辅助数组tmp用来暂时保存合并后的有序结果。主循环结束后左边或右边可能还剩下一部分元素必须补到tmp中。最后再把tmp复制回原数组。1. 为什么需要辅助数组如果直接在原数组中移动元素可能会覆盖还没有比较的数据。辅助数组相当于一个临时区域先把合并结果保存好再整体写回原数组。2. 为什么复制时使用j - left当前归并的是原数组[left, right]但辅助数组从下标0开始所以原数组 nums[j] 对应辅助数组 tmp[j - left]例如left 3时原数组下标3的元素对应tmp[0]。三、普通归并排序的 Java 代码class Solution { int[] tmp; public int[] sortArray(int[] nums) { tmp new int[nums.length]; mergeSort(nums, 0, nums.length - 1); return nums; } public void mergeSort(int[] nums, int left, int right) { if(left right) return; // 把当前区间分成左右两部分 int mid (left right) / 2; // 先让左右两部分各自有序 mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); // 合并两个有序区间 int cur1 left; int cur2 mid 1; int i 0; while(cur1 mid cur2 right) { if(nums[cur1] nums[cur2]) { tmp[i] nums[cur1]; } else { tmp[i] nums[cur2]; } } // 处理左边剩余元素 while(cur1 mid) { tmp[i] nums[cur1]; } // 处理右边剩余元素 while(cur2 right) { tmp[i] nums[cur2]; } // 把合并结果写回 nums[left..right] for(int j left; j right; j) { nums[j] tmp[j - left]; } } }复杂度数组每一层合并都需要O(n)的时间一共大约有log n层所以时间复杂度是O(n log n)。辅助数组需要O(n)的空间。四、题目一排序数组1. 题目描述给定整数数组将数组按升序排列。例如输入[5, 2, 3, 1] 输出[1, 2, 3, 5]题目链接912排序数组2. 算法思路直接使用上面的归并排序区间长度为 0 或 1 时停止递归找到中间位置递归排序左右两个区间用两个指针合并有序区间。这一题是后面几道题的基础。后面的“逆序对”“右侧更小的数字”等问题都是在合并时额外统计信息。3. 代码中的成员变量是什么int[] tmp;放在类中的变量叫成员变量。sortArray()初始化一次tmpmergeSort()的每一层递归都可以使用它。这样做的好处是不用每次进入递归都重新创建一个辅助数组。五、题目二数组中的逆序对1. 题目描述如果数组中两个位置满足i j 且 nums[i] nums[j]那么这两个数字组成一个逆序对。要求统计逆序对的总数。例如输入[7, 5, 6, 4] 输出5题目链接剑指 Offer 51数组中的逆序对2. 为什么能用归并排序把数组从中间分成左右两部分以后逆序对可以分为三类两个数字都在左半部分两个数字都在右半部分一个数字在左半部分另一个数字在右半部分。递归处理左、右区间可以得到前两类的数量。合并两个有序区间时再统计第三类的数量。3. 合并时为什么可以一次增加一段数量假设左半部分已经升序排列左边[5, 7, 9] 右边[4, 5, 8]如果当前nums[cur1] nums[cur2]由于左边是升序cur1后面的数字只会更大。因此当前右边数字不仅能和nums[cur1]组成逆序对还能和左边从cur1到mid的所有数字组成逆序对。一次增加mid - cur1 1这就是归并排序统计逆序对的关键。4. Java 代码class Solution { int[] tmp; public int reversePairs(int[] nums) { int n nums.length; tmp new int[n]; return mergeSort(nums, 0, n - 1); } public int mergeSort(int[] nums, int left, int right) { if(left right) return 0; int ret 0; int mid (left right) / 2; // 统计左边和右边内部的逆序对 ret mergeSort(nums, left, mid); ret mergeSort(nums, mid 1, right); // 统计一个来自左边、一个来自右边的逆序对 int cur1 left; int cur2 mid 1; int 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 j left; j right; j) { nums[j] tmp[j - left]; } return ret; } }5. 为什么相等时不增加数量逆序对要求前面的数严格大于后面的数nums[i] nums[j]如果两个数相等它们不构成逆序对所以代码使用nums[cur1] nums[cur2]当相等时优先放左边的数字。6. 复杂度时间复杂度是O(n log n)辅助数组空间复杂度是O(n)。六、题目三计算右侧小于当前元素的个数1. 题目描述给定数组nums返回一个新数组counts。其中counts[i]表示原数组中nums[i]右侧有多少个元素小于nums[i]。例如输入[5, 2, 6, 1] 输出[2, 1, 1, 0]解释5的右侧有2和1两个更小的数2的右侧有1一个更小的数6的右侧有1一个更小的数1的右侧没有更小的数。题目链接315计算右侧小于当前元素的个数2. 为什么只排序数字还不够归并排序过程中数字会不断移动。如果只记录数字排序以后就不知道它原来位于哪个下标。但是题目要求把答案放回原来的位置因此需要让每个数字始终和它的原始下标绑定在一起。定义int[] index; // 当前数字对应的原始下标 int[] ret; // 每个原始下标对应的答案 int[] tmpIndex; // 合并时保存下标 int[] tmpNums; // 合并时保存数字例如nums [5, 2, 6, 1] index [0, 1, 2, 3]如果数字5移动到别的位置它对应的原始下标0也必须一起移动。3. 算法思路这里使用归并排序的降序合并。当左边当前数字大于右边当前数字时由于右半部分是降序排列右边从cur2到right的数字都小于当前左边数字因此可以一次增加right - cur2 1但答案必须写回当前数字原来的位置所以写成ret[index[cur1]] right - cur2 1;4. Java 代码import java.util.ArrayList; import java.util.List; class Solution { int[] ret; int[] index; int[] tmpIndex; int[] tmpNums; public ListInteger countSmaller(int[] nums) { int n nums.length; ret new int[n]; index new int[n]; tmpIndex new int[n]; tmpNums new int[n]; // 初始化每个数字的原始下标 for(int i 0; i n; i) { index[i] i; } mergeSort(nums, 0, n - 1); ListInteger l new ArrayListInteger(); for(int x : ret) { l.add(x); } return l; } public void mergeSort(int[] nums, int left, int right) { if(left right) return; int mid (left right) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); int cur1 left; int cur2 mid 1; int 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]; } } }5.ListInteger和ArrayListInteger是什么题目要求返回一个整数列表。Java 中可以使用ListInteger l new ArrayListInteger();List是列表类型ArrayList是它的一种常用实现。使用add()可以把元素加入列表l.add(x);本地运行时通常需要导入import java.util.ArrayList; import java.util.List;6. 复杂度每一层归并都需要线性时间共有log n层因此时间复杂度是O(n log n)辅助数组空间复杂度是O(n)。七、题目四翻转对1. 题目描述如果下标满足i j并且nums[i] 2 * nums[j]那么(i, j)是一个重要翻转对要求返回翻转对的数量。例如输入[1, 3, 2, 3, 1] 输出2题目链接493翻转对2. 和逆序对的区别逆序对只要求nums[i] nums[j]翻转对要求nums[i] 2 * nums[j]它们都可以用归并排序的分治结构解决但翻转对不能直接在普通合并比较时统计。需要先利用左右两部分有序的特点用另一个指针统计满足“超过两倍”的数字然后再进行正常的合并。3. 双指针统计跨区间翻转对假设左、右两个区间都是升序排列。固定左边的nums[cur1]让cur2从右区间左端开始向右移动直到 nums[cur1] 2 * nums[cur2]在停止之前cur2左边的所有数字都满足nums[cur1] 2 * nums[cur2]所以可以一次增加一整段数量。由于左半部分是有序的当cur1向右移动时右指针不需要回退只需要继续向右。这保证了统计过程是线性的。4. Java 代码下面的代码按照降序方式合并保留了常见的tmp、ret、cur1、cur2命名class Solution { int[] tmp; public int reversePairs(int[] nums) { int n nums.length; tmp new int[n]; return mergeSort(nums, 0, n - 1); } public int mergeSort(int[] nums, int left, int right) { if(left right) return 0; int ret 0; int mid (left right) / 2; // 统计左边和右边内部的翻转对 ret mergeSort(nums, left, mid); ret mergeSort(nums, mid 1, right); // 先统计一个来自左边、一个来自右边的翻转对 int cur1 left; int cur2 mid 1; int i left; while(cur1 mid) { while(cur2 right nums[cur2] nums[cur1] / 2.0) { cur2; } if(cur2 right) { break; } ret right - cur2 1; cur1; } // 再按降序合并两个有序区间 cur1 left; cur2 mid 1; while(cur1 mid cur2 right) { if(nums[cur1] nums[cur2]) { tmp[i] nums[cur2]; } else { tmp[i] nums[cur1]; } } 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; } }5. 为什么代码中使用/ 2.0题目条件是nums[cur1] 2 * nums[cur2]把它变形以后可以写成nums[cur2] nums[cur1] / 2.0使用2.0是为了进行浮点除法避免整数除法截断造成边界判断错误。例如5 / 2的整数结果是2而5 / 2.0是2.5。另外如果直接写2 * nums[cur2]当数字很大时可能发生整数溢出使用除法形式可以避免这一处乘法溢出。6. 复杂度每一层递归中统计翻转对和合并都只需要线性时间因此总时间复杂度是O(n log n)辅助数组需要O(n)空间。八、4 道题共同形成的归并排序规律规律一所有题都可以拆成“左边、右边、合并”普通排序是左边排好序 右边排好序 合并逆序对是左边的逆序对 右边的逆序对 跨左右的逆序对翻转对也是同样的三部分只是跨区间的判断条件变成了“左边大于右边的两倍”。规律二区间有序后可以一次统计一整段逆序对中ret mid - cur1 1;右侧更小元素个数中ret[index[cur1]] right - cur2 1;这些语句都不是只统计一个数字而是利用有序性一次统计一整段。规律三需要返回原始位置时数字必须和下标绑定315 题中的index不是排序下标而是每个数字最开始在原数组中的下标。数字移动时下标也必须同步移动nums[j] tmpNums[j - left]; index[j] tmpIndex[j - left];否则最后的统计结果会写错位置。规律四普通归并和特殊统计要分清先后普通归并只关心谁大谁小翻转对关心的是“是否超过两倍”因此需要在正式合并之前先完成特殊条件的统计。九、常见 Java 写法创建辅助数组tmp new int[nums.length];获取数组长度nums.length创建整数列表ListInteger l new ArrayListInteger();三目运算符归并代码中常见tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2];它等价于if(nums[cur1] nums[cur2]) { tmp[i] nums[cur1]; } else { tmp[i] nums[cur2]; }刚开始学习时可以先使用if-else等逻辑熟悉以后再使用三目运算符简化代码。十、这一阶段的总结归并排序最值得掌握的不是“排序数组”这一道题而是“合并两个有序区间时可以顺便统计信息”这一思想。普通排序合并时选择较小元素逆序对右边当前元素较小时一次统计左边剩余数量右侧更小元素个数数字和原始下标绑定把统计结果写回原位置翻转对先用双指针统计“超过两倍”的数量再正常合并。我现在遇到这类题时会先写出普通归并排序的四个步骤递归出口、找中点、递归左右、合并还原。然后再思考题目要求统计的关系能不能利用左右区间已经有序这一点一次性计算出来。这样做比直接面对整道困难题更容易找到突破口。