题目描述

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

思路

1. 遍历数组,将每个遍历的数插入到前面已经排好序的数组中,将前插的步数作为逆序对的总数P(只过了50%的用例,可能是时间超了)
2. 归并排序,找出中间点mid,两边都是排好序的数组,左边若大于右边->左边剩下的所有都大于右边这个值

实现

归并排序实现

    public int InversePairs(int [] array) {
        return merge(array, 0, array.length-1);
    }

    public int merge(int[] nums, int start, int end){
        if(start>=end){
            return 0;
        }
        int mid=(start+end)/2;
        int count=0;
        count+=merge(nums, start, mid);
        count+=merge(nums,mid+1, end);

        // mid为中心左右各一半
        int[] temp=new int[end-start+1];
        int i=start;
        int j=mid+1;
        int p=0;
        while(i<=mid&&j<=end){
            if(nums[i]<nums[j]){
                temp[p++]=nums[i++];
            }else{
                //注意:这里不加%1000000007会有问题
                count=(count+(mid-i+1))%1000000007;
                temp[p++]=nums[j++];
            }
        }
        if(i<=mid){
            while(i<=mid){
                temp[p++]=nums[i];
                i++;
            }
        }
        if(j<=end){
            while(j<=end){
                temp[p++]=nums[j];
                j++;
            }
        }
        for(int k=0;k<end-start+1;k++){
            nums[start+k]=temp[k];
        }
        return count;
    }

往前插入排序（时间超时）

public int InversePairs(int [] array) {
        if(array.length==0){
            return 0;
        }
        int count=0;
        for(int i=1;i<array.length;i++){
            //小于最大值
            if(array[i]<array[i-1]){
                int j=i-1;
                int temp=array[i];
                while(j>=0&&array[j]>temp){
                    count++;
                    j--;
                }
                j++;
                //平移数组
                for(int k=i;k>j;k--){
                    array[k]=array[k-1];
                }
                array[j]=temp;
            }
        }
        return count%1000000007;
    }
}