数组中的逆序对

题目描述

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

输入描述

题目保证输入的数组中没有的相同的数字

数据范围：

    对于%50的数据,size<=10^4

    对于%75的数据,size<=10^5

    对于%100的数据,size<=2*10^5

示例

输入

1,2,3,4,5,6,7,0

输出

7

思路

1.可以通过移动数字发现，计算逆序对的方式和归并排序的merge操作有相似之处。
2.当进行merge操作时，若左边数组的元素大于右边数组的某一元素时，说明存在mid-left-l个逆序对。

• 因为左边数组和右边数组都是排好序的
• l索引代表左边数组当前索引

3. 可以参照下图，理解归并过程中的计算逻辑。

Java代码实现

public class Solution {
    private int count = 0;
    public int InversePairs(int [] array) {
        if(array != null){
            mergeSort(array,0,array.length-1);
        }
        return count;
    }


    private void mergeSort(int[] array,int left,int right){
        if(left >= right){
            return ;
        }
        int mid = (left + right)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,mid+1,right);
    }

    private void merge(int[] array,int left,int mid,int right){

        int[] leftArray = new int[mid-left];
        int[] rightArray = new int[right-mid+1];

        for(int i=left;i<mid;i++){
            leftArray[i-left] = array[i];
        }

        for(int i=mid;i<=right;i++){
            rightArray[i-mid] = array[i];
        }

        int l = 0;
        int r = 0;
        int k = left;

        while(l < leftArray.length && r < rightArray.length){
            if(leftArray[l] > rightArray[r]){
                array[k++] = rightArray[r++];
                count = (count + mid - left- l)%1000000007;
            }else{
                array[k++] = leftArray[l++];
            }
        }

        while(l < leftArray.length){
            array[k++] = leftArray[l++];
        }

        while(r < rightArray.length){
            array[k++] = rightArray[r++];
        }
    }
}

Golang代码实现

var res int = 0

func InversePairs(nums []int) int {
    mergeOuter(nums,0,len(nums)-1)
    return res
}

func mergeOuter(nums[] int,left int,right int){
    if left >= right{
        return
    }
    mid := (left + right)/2
    mergeOuter(nums,left,mid)
    mergeOuter(nums,mid+1,right)
    merge(nums,left,mid+1,right)
}

func merge(nums []int,left int,mid int,right int){
    leftArray := make([]int,mid-left)
    rightArray := make([]int,right-mid+1)

    for i:=left; i<mid;i++{
        leftArray[i-left] = nums[i];
    }

    for i:=mid; i<=right;i++ {
        rightArray[i-mid] = nums[i];
    }

    k := left
    l,r := 0,0

    for l<len(leftArray) && r<len(rightArray) {
        if leftArray[l] > rightArray[r]{
            nums[k] = rightArray[r]
            k++
            r++
            res = (res + mid - left - l)%1000000007
        }else{
            nums[k] = leftArray[l]
            k++
            l++
        }
    }

    for l<len(leftArray) {
        nums[k] = leftArray[l]
        k++
        l++
    }

    for r<len(rightArray){
        nums[k] = rightArray[r]
        k++
        r++
    }
}