在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
解答
（已经发布在了中文leetcode网站
和官方解答里面一样，使用了归并排序的方法，在这个过程中添加了对应的逆序对的个数。
- 用归并排序
- 归并的时候，我们可以检测逆序对有多少个
- 比如现在要归并【1,3,6,19】和【2,9,10,20】
- 那么我们可以看到逆序数是：
- 3和2，6和2，19和2,9,10
- 如果是有两个指针，前一个指针需要移动的时候需要记录一下上一个数字。
- 下面用一个例子说明，两个数字分别代表两个指针指向的数：
- 1 2，之后移动了第一个指针，第二个指针的index是0（也就是1比后面几个大）
- 3 2，之后移动第二个
- 3 9，之后移动第一个，第二个指针的index是1（也就是3比后面几个大）
- 6 9，之后移动第一个，第二个指针的index是1（也就是6比后面几个大）
- 19 9，移动第二个
- 19 10，移动第二个
- 19 20，移动第一个，第二个指针的index是3（也就是19比后面几个大）
- 这样我们把这几个数字对应的逆序对的个数都找到了！加起来就好了！
- 如果是【1,3,6,19,90】和【2,9,10,20,30】，这时候到最后会发现两个指针分别指向90和结束的位置，这时候把第一个数组后面的元素加进来，一直加上第二个指针的index（5，这时候指向空）就可以了。
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class Solution {
public:
int merge_sort(vector<int>& nums, vector<int>& aux, int start, int end) {
if (start >= end) {
return 0;
}
int ans = 0;
int mid = (end + start) / 2;
ans += merge_sort(nums, aux, start, mid);
ans += merge_sort(nums, aux, mid + 1, end);
int index1 = start;
int index2 = mid + 1;
int tar = start;
while (index1 <= mid && index2 <= end) {
if (nums[index1] <= nums[index2]) {
ans += index2 - mid - 1;
aux[tar++] = nums[index1++];
}
else {
aux[tar++] = nums[index2++];
}
}
while (index1 <= mid) {
ans += index2 - mid - 1;
aux[tar++] = nums[index1++];
}
while (index2 <= end) {
aux[tar++] = nums[index2++];
}
for (int i = start; i <= end; i++) {
nums[i] = aux[i];
}
return ans;
}
int reversePairs(vector<int>& nums) {
int len = nums.size();
vector<int> aux(len, 0);
return merge_sort(nums, aux, 0, len - 1);
}
};
|