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
|
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
public class InversionCount {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
// int[] b = new int[n];
System.out.println(getInversionCountFromArray(a));
scanner.close();
}
public static long getNumberOfInversions(int[] a, int[] b, int left, int right) {
long numberOfInversions = 0;
if (right <= left + 1) {
return numberOfInversions;
}
int middle = (left + right) / 2;
numberOfInversions += getNumberOfInversions(a, b, left, middle);
numberOfInversions += getNumberOfInversions(a, b, middle, right);
// write your code here
return numberOfInversions;
}
public static long getInversionCountFromArray(int[] a) {
List<Integer> aList = Arrays.stream(a).boxed().collect(Collectors.toList());
List<Integer> D = new ArrayList<Integer>();
long numberOfInversions = getInversionCountFromList(aList, D);
return numberOfInversions;
}
private static long getInversionCountFromList(List<Integer> A, List<Integer> D) {
long numberOfInversions = 0;
if (A.size() == 1) {
D.add(A.get(0));
return 0;
}
int m = A.size() / 2;
List<Integer> D1 = new ArrayList<Integer>();
numberOfInversions += getInversionCountFromList(new ArrayList<Integer>(A.subList(0, m)), D1);
List<Integer> D2 = new ArrayList<Integer>();
numberOfInversions += getInversionCountFromList(new ArrayList<Integer>(A.subList(m, A.size())), D2);
// long mergeCount = mergeInversionCount(new ArrayList<Integer>(A.subList(0, m)), new ArrayList<Integer>(A.subList(m, A.size())));
long mergeCount = mergeInversionCount(D1, D2, D);
return numberOfInversions + mergeCount;
}
private static long mergeInversionCount(List<Integer> B, List<Integer> C, List<Integer> D) {
long count = 0;
while (B.size() != 0 && C.size() != 0) {
int b = B.get(0);
int c = C.get(0);
if (b <= c) {
D.add(b);
B.remove(0);
} else {
count += B.size();
D.add(c);
C.remove(0);
}
}
D.addAll(B);
D.addAll(C);
return count;
}
public static int[] mergeSortArray(int[] a) {
List<Integer> aList = Arrays.stream(a).boxed().collect(Collectors.toList());
List<Integer> sortedList = mergeSortList(aList);
return sortedList.stream().mapToInt(i -> i).toArray();
}
private static List<Integer> mergeSortList(List<Integer> A) {
if (A.size() == 1)
return A;
int m = A.size() / 2;
List<Integer> B = mergeSortList(new ArrayList<Integer>(A.subList(0, m)));
List<Integer> C = mergeSortList(new ArrayList<Integer>(A.subList(m, A.size())));
List<Integer> aPrime = mergeList(B, C);
return aPrime;
}
private static List<Integer> mergeList(List<Integer> B, List<Integer> C) {
List<Integer> D = new ArrayList<>();
while (B.size() != 0 && C.size() != 0) {
int b = B.get(0);
int c = C.get(0);
if (b <= c) {
D.add(b);
B.remove(0);
} else {
D.add(c);
C.remove(0);
}
}
D.addAll(B);
D.addAll(C);
return D;
}
}
|
