-
Notifications
You must be signed in to change notification settings - Fork 2
/
剑指Offer51.数组中的逆序对.html
130 lines (108 loc) · 3.62 KB
/
剑指Offer51.数组中的逆序对.html
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>剑指 Offer 51. 数组中的逆序对</title>
</head>
<body>
<script>
// https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
// 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function (nums) {};
// --- answer-0 ---
// 暴力
var reversePairs = function (nums = []) {
if (nums.length < 2) return 0;
let res = 0;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] > nums[i]) res++;
}
}
return res;
};
// 拒绝暴力超时
// --- answer-0 ---
// --- answer-1 ---
// 动态不了
// 借鉴归并排序， 分治
// 时间复杂度：同归并排序 O(nlogn) 空间复杂度：同归并排序 O(n)
function reversePairs(nums) {
if (nums.length < 2) return 0;
return reverse(nums, 0, nums.length - 1, []);
}
function reverse(nums, left, right, temp) {
if (left >= right) return 0;
let mid = left + ((right - left) >> 1);
let leftPairs = reverse(nums, left, mid, temp);
let rightPairs = reverse(nums, mid + 1, right, temp);
// 已然有序 无跨区间的逆序对
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
// 跨区间的逆序对
let crossPairs = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
function mergeAndCount(nums, left, mid, right, temp) {
for (let i = left; i <= right; i++) {
temp[i] = nums[i];
}
let i = left;
let j = mid + 1;
// 排序的过程同时 统计逆序对
let count = 0;
for (let k = left; k <= right; k++) {
// 越界处理
if (i == mid + 1) {
nums[k] = temp[j];
j++;
} else if (j == right + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
// 比较处理
// 去掉等号就不是稳定的了
nums[k] = temp[i];
i++;
} else {
nums[k] = temp[j];
j++;
count += mid - i + 1;
}
}
return count;
}
// 原 2 3 5 7 | 1 4 6 8
// 辅 2 3 5 7 | 1 4 6 8
// =>
// 原 1 3 5 7 | 1 4 6 8
// 辅 2 3 5 7 | 4 6 8
// => 1的逆序数就是 左边数组的个数
// 原 1 2 5 7 | 1 4 6 8
// 辅 3 5 7 | 4 6 8
// 原 1 2 3 7 | 1 4 6 8
// 辅 5 7 | 4 6 8
// 原 1 2 3 4 | 1 4 6 8
// 辅 5 7 | 6 8
// => 4的逆序数就是 左边数组的个数
// 在归并的同时统计逆序数， 使用这个的条件是子区间分别有序
// --- answer-1 ---
var nums = [7, 5, 6, 4];
var result = 5; // [7,5] [7,6] [7,4] [5,4] [6, 4]
nums = [7, 5, 6, 4, 4];
result = 8;
nums = [7, 5, 6, 4, 4, 5, 4, 3, 1];
result = 29;
console.log('nums = ', nums);
console.log('result = ', result);
console.log('reversePairs = ', reversePairs(nums));
</script>
</body>
</html>