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
|
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
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] }
copy.length = 0
return count }
const arr = [7, 5, 6, 4] console.log(findInversePairNum(arr, 0, arr.length - 1)) console.log(arr)
|