题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
题目保证输入的数组中没有的相同的数字
public class Solution {
int cnt;
public int InversePairs(int[] array) {
cnt = 0;
if (array != null)
mergeSort(array, 0, array.length - 1);
return cnt;
}
/*
* 归并排序
*/
public void mergeSort(int[] a, int start, int end) {
if (start >= end)
return;
int mid = (start + end) >> 1;
mergeSort(a, start, mid);
mergeSort(a, mid + 1, end);
merge(a, start, mid, end);
}
/*
* 将一个数组中的两个相邻有序区间合并成一个
*/
public void merge(int[] a, int start, int mid, int end) {
int[] tmp = new int[end - start + 1];
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (a[i] <= a[j])
tmp[k++] = a[i++];
else {
tmp[k++] = a[j++];
cnt += mid - i + 1; // 计算逆序对
}
}
while (i <= mid)
tmp[k++] = a[i++];
while (j <= end)
tmp[k++] = a[j++];
for (k = 0; k < tmp.length; k++)
a[start + k] = tmp[k];
}
}
