【剑指offer】【Java】数组中的逆序对

题目

链接:https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
来源:牛客网

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

代码

注意点:

  • 归并排序:Java不能切片,所以用start,end,mid控制数组内切片长度
  • Java
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
public class Solution {
private int count;
public int InversePairs(int [] array) {
count = 0;
if(array != null){
mergeSort(array, 0, array.length - 1);
}
return count;
}

private void mergeSort(int[] a, int start, int end){
if(start >= end)
return;
int mid = start + (end - start) / 2;
mergeSort(a, start, mid);
mergeSort(a, mid+1, end);
merge(a,start,mid,end);
}

private void merge(int[] a, int start, int mid, int end){
int[] temp = new int[end-start+1];
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (a[i] <= a[j])
temp[k++] = a[i++];
else {
temp[k++] = a[j++];
// ai大于aj,由于归并,所以相反的必定是和所有前面的数字,所以是mid到最左边i中间的数的个数
count = (count + mid - i + 1) % 1000000007;
}
}

while (i <= mid)
temp[k++] = a[i++];
while (j <= end)
temp[k++] = a[j++];
for(k=0;k<temp.length;k++){ //将临时数组的数字写回a数组!
a[start+k] = temp[k];
}
}
}