企业官网建设流程全解析

目录

一、归并排序的基本思想

二、合并两个有序区间

1. 为什么需要辅助数组

2. 为什么复制时使用 j - left

三、普通归并排序的 Java 代码

复杂度

四、题目一：排序数组

五、题目二：数组中的逆序对

六、题目三：计算右侧小于当前元素的个数

七、题目四：翻转对

八、4 道题共同形成的归并排序规律

规律一：所有题都可以拆成“左边、右边、合并”

规律二：区间有序后，可以一次统计一整段

规律三：需要返回原始位置时，数字必须和下标绑定

规律四：普通归并和特殊统计要分清先后

九、常见 Java 写法

创建辅助数组

获取数组长度

创建整数列表

三目运算符

十、这一阶段的总结

归并排序最有价值的地方，不只是把数组排好序，而是可以利用“左右两部分已经有序”这一条件，在合并过程中顺便统计很多信息。

这篇文章从 4 道题开始：普通排序、数组中的逆序对、计算右侧小于当前元素的个数，以及翻转对。前 3 道题逐步增加难度，最后一题会展示如何在归并之前使用双指针统计特殊的大小关系。

本文涉及的题目链接：

• 912：排序数组
• 剑指 Offer 51：数组中的逆序对
• 315：计算右侧小于当前元素的个数
• 493：翻转对

一、归并排序的基本思想

归并排序体现的是“先拆开，再合并”的过程。

对于数组区间[left, right]：

1. 找到中间位置mid；
2. 把区间拆成[left, mid]和[mid + 1, right]；
3. 递归处理左半部分；
4. 递归处理右半部分；
5. 将两个已经有序的部分合并起来。

一直拆到区间中只剩一个元素。一个元素天然是有序的，然后再从小区间开始逐步合并，最终得到完整的有序数组。

归并排序的固定结构是：

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()初始化一次tmp，mergeSort()的每一层递归都可以使用它。

这样做的好处是，不用每次进入递归都重新创建一个辅助数组。

五、题目二：数组中的逆序对

1. 题目描述

如果数组中两个位置满足：

i < j 且 nums[i] > nums[j]

那么这两个数字组成一个逆序对。要求统计逆序对的总数。

例如：

输入：[7, 5, 6, 4] 输出：5

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

2. 为什么能用归并排序

把数组从中间分成左右两部分以后，逆序对可以分为三类：

1. 两个数字都在左半部分；
2. 两个数字都在右半部分；
3. 一个数字在左半部分，另一个数字在右半部分。

递归处理左、右区间，可以得到前两类的数量。合并两个有序区间时，再统计第三类的数量。

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 List<Integer> 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); List<Integer> l = new ArrayList<Integer>(); 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.List<Integer>和ArrayList<Integer>是什么

题目要求返回一个整数列表。Java 中可以使用：

List<Integer> l = new ArrayList<Integer>();

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

创建整数列表

List<Integer> l = new ArrayList<Integer>();

三目运算符

归并代码中常见：

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，等逻辑熟悉以后再使用三目运算符简化代码。

十、这一阶段的总结

归并排序最值得掌握的不是“排序数组”这一道题，而是“合并两个有序区间时可以顺便统计信息”这一思想。

• 普通排序：合并时选择较小元素；
• 逆序对：右边当前元素较小时，一次统计左边剩余数量；
• 右侧更小元素个数：数字和原始下标绑定，把统计结果写回原位置；
• 翻转对：先用双指针统计“超过两倍”的数量，再正常合并。

我现在遇到这类题时，会先写出普通归并排序的四个步骤：递归出口、找中点、递归左右、合并还原。然后再思考：题目要求统计的关系，能不能利用左右区间已经有序这一点一次性计算出来。这样做比直接面对整道困难题更容易找到突破口。