描述

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

示例1

输入：[1,2,3,4,5,6,7,0]

返回值：7

第一种解法，暴力解法，循环遍历，把所有情况依次统计出来，代码如下，但是很遗憾，功能没问题，由于时间过长，不能通过所有测试用例。所以提交显示不通过。

public int firstInversePairs(int [] array) {    int count = 0;    if(null == array || array.length < 1){        return 0;    }    for (int i = 0; i < array.length; i++) {        int num = array[i];        for (int j = i+1; j < array.length; j++) {            if(num > array[j]){                count++;            }        }    }    return count%1000000007;}

第二种解法，我也是看了别人的思路，才整出来的，简单来说，使用归并排序来解决问题，归并排序是基础，在排序的过程中，判断逆序对的数量即可。代码如下

 private  int count = 0;public int secondInversePairs(int [] array) {        if(null == array || array.length < 1){            return count;        }        int[] tmp = new int[array.length];        mergeSort(array,0,array.length-1,tmp);        return count % 1000000007;    }    public void mergeSort(int[] arr, int start,int end,int[] tmp){        if(start < end){            int mid = (start + end)/2;            mergeSort(arr,start,mid,tmp);            mergeSort(arr,mid+1,end,tmp);            merge(arr,tmp,start,end,mid);        }    }    public void merge(int[] arr,int[] tmp,int left,int right,int mid){        int i = left;        int j = mid + 1;        int k = 0;        while (i <= mid && j <= right ){            if(arr[i] < arr[j]){                tmp[k++] = arr[i++];            }else {                tmp[k++] = arr[j++];                count = (count + mid - i + 1) % 1000000007;            }        }        while (i <= mid){            tmp[k++] = arr[i++];        }        while (j <= right){            tmp[k++] = arr[j++];        }        k = 0;        for ( i = left; i <= right; i++) {            arr[i] = tmp[k++];        }    }