Question

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

思路：归并排序的思想。

对于本题，在两个子序列left、right合并过程中，当left中当前元素A大于right中当前元素B时，因为left序列已经有序，所以A后面所有元素都可以与B组成逆序对。

public class Solution {
  int[] aux;
  int count = 0;
  public int InversePairs(int [] array) {
    aux = new int[array.length];
    mergeSort(array, 0, array.length-1);
    return count;
  }
  private void merge(int[] array, int l, int m, int h){
    int i = l, j = m+1;
    for(int k = l; k <= h; k++){
      aux[k] = array[k];
    }
    for(int k = l; k <= h; k++){
      if(i > m){
        array[k] = aux[j++];
      }else if(j > h){
        array[k] = aux[i++];
      }else if(aux[i] <= aux[j]){
        array[k] = aux[i++];
      }else{
        array[k] = aux[j++];
        count = (count + m + 1 - i)%1000000007;
      }
    }
  }
  private void mergeSort(int[] array, int l, int h){
    if(l>=h) return;
    int m = l + (h-l)/2;
    mergeSort(array,l,m);
    mergeSort(array,m+1,h);
    merge(array,l,m,h);
  }
}