题目描述

　　

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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){2         Solution36 solution36 = new Solution36();3         int[] array = new int[]{3,3,2,4,2,1};4         int count = solution36.InversePairs(array);5         System.out.println(count);6         for (Integer i: array) {7             System.out.print(i + "　");8         }9     }