归并排序是我们经常使用的一种排序方法，其特性为：
最差时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
最差空间复杂度：O(n)
稳定性：稳定
本文主要介绍在LeetCode中用到归并排序的两道例题，详细展示一下归并排序的强大应用；
归并排序
下面的代码是使用c++的vector编写的归并排序，方便读者阅读理解归并排序：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
void MergeSort(vector<int> &nums, int left, int right)
{
if(right - left <= 1)
return;
int mid = (left + right) / 2;
MergeSort(nums, left, mid);
MergeSort(nums, mid, right);
vector<int> temp(right - left, 0);
int l = left;
int r = mid;
int s = 0;
while(l < mid && r < right)
{
if(nums[l] < nums[r])
temp[s++] = nums[l++];
else
temp[s++] = nums[r++];
}
while(l < mid)
temp[s++] = nums[l++];
while(r < right)
temp[s++] = nums[r++];
for(int i = left; i < right; ++i)
nums[i] = temp[i-left];
}
int main()
{
vector<int> nums;
int num;
while(cin >> num)
nums.push_back(num);
for(const auto x : nums)
cout << x << " ";
cout << endl;
MergeSort(nums, 0, nums.size());
for(const auto x : nums)
cout << x << " ";
cout << endl;
return 0;
}
归并排序应用
315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
- To the right of 5 there are 2 smaller elements (2 and 1).
- To the right of 2 there is only 1 smaller element (1).
- To the right of 6 there is 1 smaller element (1).
- To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
解题思路
以[5, 2, 6, 1]为例，我们使用归并排序解决这个问题：
首先归并排序将[5, 2, 6, 1]分为
[5, 2],[6, 1]
然后因为再归并的话可以得到
[[5], [2]],[[6], [1]]
在[[6], [1]]中，[1]位于整个区间的右部，所以结果为0；[6]位于左边，使[6]中每个元素都与右边[1]比较，可以得到6的count值为1；比较完成后对[[6], [1]]进行排序，得到：
[[5], [2]],[[1], [6(1)]]
然后在[[5], [2]]中执行相同的操作，2的count值为0， 5的count值为1，得到：
[[2], [5(1)]],[[1], [6(1)]]
然后在[[[2], [5(1)]], [[1], [6(1)]]]中进行比较，左边[[2], [5(1)]]中每个数值都在[[1], [6(1)]]进行遍历计数，由于[[1], [6(1)]]和[[2], [5(1)]]都已经排好序了，所以只需要遍历一遍就可以得到结果：
[[2(1)], [5(2)]],[[1], [6(1)]]
每次通过辅助的拷贝数组将计数信息保存到正确的位置即可；
由于使用了归并排序，所以每次进行比较的时候都是比较的有序队列，这样可以很好地提高效率，同时也保证了每一轮次左右相对位置的稳定；
代码
1 | class Solution |
327. Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.
解题思路
这一题跟上面一题类似，都要使用归并排序进行分段求解；
首先构建一个sum的数组，sum[i]表示从0～i的子区间的元素之和，这样sum[i][j]就表示从i～j的子区间的元素之和，从而问题也就转化为求取sum数组中sum[i]之后的sum[j]满足lower <= sum[j] - sum[i] <= upper的个数，其中i<=j，就相当于上面那个题加了一个上下界；
则仍然使用上面归并排序的思路，在归并排序的过程中进行计数计算，对于左边的每个元素，都在右边的元素中去找两个参数:
left：第一个满足sum[j] - sum[i] >= lower，即为左边界；right：第一个满足sum[j] - sum[i] > upper，即为右边界；
则right-left即为所求的计数个数，不断叠加即可；
因为每一次归并之后左右两个部分都是有序的序列，所以这里left和right同样只需要扫描一遍即可；
代码
1 | class Solution |