1. 题目描述

输入一个数组,求出这个数组中的逆序对的总数。

例如在数组{7,5,6,4}中,一共存在 5 个逆序对,分别是(7,6), (7, 5), (7,4), (6,4), (5,4)。

2. 思路分析

暴力法的时间复杂度是 O(N^2)。利用归并排序的思路,可以将时间复杂度降低到 O(NlogN)。

比如对于 7、5、6、4 来说,会被分成 5、7 和 4、6 两组。

准备两个指针指向两组最后元素,当左边数组指针的对应元素小于右边指针对应元素,结果可以加上从左指针到右指针之间的元素个数(都是逆序的)。

依次移动指针,直到达到边界。

3. 代码实现

代码最后输出了数组,经过归并,数组已经是有序的了。

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
/**
*
* @param {Array} arr
* @param {Number} start
* @param {Number} end
* @return {Number}
*/
function findInversePairNum(arr, start, end) {
if (start === end) {
return 0
}

const copy = new Array(end - start + 1)
const length = (end - start) >> 1
const leftNum = findInversePairNum(arr, start, start + length)
const rightNum = findInversePairNum(arr, start + length + 1, end)

let i = start + length, // 左子数组的最后一个下标
j = end, // 右子数组的最后一个下标
count = leftNum + rightNum,
copyIndex = end - start // copy数组中的最后一个下标

// 可以参考数据集合:[2, 3, 1, 4]
for (; i >= start && j >= start + length + 1; ) {
if (arr[i] > arr[j]) {
copy[copyIndex--] = arr[i--]
count += j - start - length
} else {
copy[copyIndex--] = arr[j--]
}
}

for (; i >= start; --i) {
copy[copyIndex--] = arr[i]
}

for (; j >= start + length + 1; --j) {
copy[copyIndex--] = arr[j]
}

// 将排序号的数据放到原数组中
for (i = 0; i < end - start + 1; ++i) {
arr[i + start] = copy[i]
}

// clear
copy.length = 0

return count
}

/**
* 测试代码
*/

const arr = [7, 5, 6, 4]
console.log(findInversePairNum(arr, 0, arr.length - 1)) // output: 5
console.log(arr) // output: [4, 5, 6, 7]