题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。 即输出P%1000000007
本题采用归并排序，归并排序算法我在前一篇博客里写到过，在那个基础上进行修改即可！(强烈建议先理解归并排序的具体算法后，再来做此题)
public class Solution36 {
private int count = 0; //记录次数
private int[] copy ;
public int InversePairs(int [] array) {
if(array.length == 0) return 0;
copy = new int[array.length];
sort(array, 0, array.length-1);
return count%1000000007;
}
private void sort(int[] array, int start, int end) {
if(end <= start) return;
//int mid = start + (end - start) / 2;
int mid = (end+start) /2;
sort(array, start, mid);//左边数组排序
sort(array, mid + 1, end);//右边数组排序
merge(array,start,mid, end); //归并方法
}
/**
* 排序
* @param array 需要排序的数组
* @param start 数组的起始位置
* @param mid 数组的中间位置
* @param end
*/
private void merge(int[] array, int start, int mid, int end) {
int i = start, j = mid + 1; //将数组分割成两段，由于归并排序特点，前后两段是有序的
for(int k = start; k <= end; k++){ //复制数组
copy[k] = array[k];
}
for(int k= start; k<= end; k++){
if(i > mid) array[k] = copy[j++]; //当只剩下右边数组
else if(j > end) array[k] = copy[i++]; //当只剩下左边数组
else if(copy[i] > copy[j]) {//当前一个数组的数大于后一个数组的数时，逆序(前后数组分界点为mid)
/**
* 例如数组5 6 7 2 4 8进行归并 ，因为归并排序会使数组前后数组有序
* 前一个数组为:5 6 7 ,后一个数组为: 2 4 8
* 当 5 大于 2时，5后面的6,7都会大于2， 且5的最后一个数组下标为mid,
* 所以count = count+ mid - i + 1 然后将2添加到array[k]中
*/
count = (count + mid-i + 1)%1000000007;
array[k] = copy[j++];
}else {
array[k] = copy[i++];
}
}
}
}
测试代码:
1 public static void main(String[] args){
Solution36 solution36 = new Solution36();
int[] array = new int[]{3,3,2,4,2,1};
int count = solution36.InversePairs(array);
System.out.println(count);
for (Integer i: array) {
System.out.print(i + " ");
}
}