題目描述
在數(shù)組中的兩個數(shù)字痴怨，如果前面一個數(shù)字大于后面的數(shù)字厅目，則這兩個數(shù)字組成一個逆序?qū)σ住］斎胍粋€數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P咆瘟。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007
public class Solution {
int sum = 0;
public int InversePairs(int[] array) {
if(array == null || array.length == 0)
return 0;
mSort(array, 0, array.length - 1);
return sum%1000000007;
}
private void mSort(int[] a, int left, int right) {
if(left >= right)
return;
int mid = (left + right) / 2;
mSort(a, left, mid);
mSort(a, mid + 1, right);
merge(a, left, mid, right);
}
private void merge(int[] a, int left, int mid, int right) {
int i = mid;
int j = right;
int[] temp = new int[right - left + 1];
int k = temp.length - 1;
while(i >= left && j > mid) {
if(a[i] <= a[j]) {
temp[k] = a[j];
j --;
k --;
}else {
sum += (j - mid);
sum %= 1000000007;
temp[k] = a[i];
k --;
i --;
}
}
while(i >= left) {
temp[k] = a[i];
i --;
k --;
}
while( j > mid) {
temp[k] = a[j];
j --;
k --;
}
k = 0;
for(int n = left; n <= right; n ++)
a[n] = temp[k ++];
}
public static void main(String[] args) {
Solution obj = new Solution();
int[] a = {};
obj.InversePairs(a);
for(int i : a)
System.out.println(i);
System.out.println(obj.InversePairs(a));
}
}
