JZ35-数组中的逆序对
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
public class Solution {
int count = 0;
public int InversePairs(int[] array) {
if (array == null || array.length <= 1) {
return 0;
}
mergeSort(array, 0, array.length - 1);
return count;
}
public void mergeSort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int mid = start + ((end - start) >> 1);
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, end);
}
public void merge(int[] array, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (array[i] <= array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
count = (count + (mid - i + 1)) % 1000000007; //不能+=；而且不能在上面取余
}
}
while (i <= mid) {
temp[k++] = array[i++];
}
while (j <= end) {
temp[k++] = array[j++];
}
for(int l=start;l<=end;l++){
array[l] = temp[l-start];
}
}
} 