描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个 逆序对 。输入一个数组,求出这个数组中的逆序对的总数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++];
}
}