数组中的逆序对
问题:
【解决】
① 采用归并的思想。
public class Solution {
public static void main(String[] args) {
int[] array = {7,5,6,4};
System.out.println(InversePairs(array));
}
public static int InversePairs(int [] array) {
int count = divideSort(array,0,array.length - 1);
return count;
}
public static int divideSort(int[] array,int start,int end){
int count = 0;
if (start < end){
int mid = (end - start) / 2 + start;
count += divideSort(array,start,mid) % 1000000007;
count += divideSort(array,mid + 1,end) % 1000000007;
count += merge(array,start,mid,end) % 1000000007;
}
return count % 1000000007;
}
public static int merge(int[] array,int start,int mid,int end){
int[] tmp = new int[end - start + 1];
int count = 0;
if (start < end){
int p = tmp.length - 1;
int p1 = mid;
int p2 = end;
while (p1 >= start && p2 >= mid + 1){
if (array[p1] > array[p2]){
count += p2 - mid;
count %= 1000000007;
tmp[p --] = array[p1 --];
}else {
tmp[p --] = array[p2 --];
}
}
while (p1 >= start){
tmp[p --] = array[p1 --];
}
while (p2 >= mid + 1){
tmp[p --] = array[p2 --];
}
for (int i = 0;i < tmp.length;i ++){
array[i + start] = tmp[i];
}
}
return count % 1000000007;
}
}
转载于:https://my.oschina.net/liyurong/blog/1637804