forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode03_ReversePair.java
More file actions
130 lines (119 loc) · 2.87 KB
/
Code03_ReversePair.java
File metadata and controls
130 lines (119 loc) · 2.87 KB
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
package class04;
public class Code03_ReversePair {
public static int reverPairNumber(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
// arr[L..R]既要排好序，也要求逆序对数量返回
// 所有merge时，产生的逆序对数量，累加，返回
// 左 排序 merge并产生逆序对数量
// 右 排序 merge并产生逆序对数量
public static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
// l < r
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int L, int m, int r) {
int[] help = new int[r - L + 1];
int i = help.length - 1;
int p1 = m;
int p2 = r;
int res = 0;
while (p1 >= L && p2 > m) {
res += arr[p1] > arr[p2] ? (p2 - m) : 0;
help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
}
while (p1 >= L) {
help[i--] = arr[p1--];
}
while (p2 > m) {
help[i--] = arr[p2--];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return res;
}
// for test
public static int comparator(int[] arr) {
int ans = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
ans++;
}
}
}
return ans;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (reverPairNumber(arr1) != comparator(arr2)) {
System.out.println("Oops!");
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println("测试结束");
}
}