数组中的逆序对

题目

解题思路

1、暴力破解

2、排序的方式，归并排序

• 将数组从中间划分成两半，逆序对的结果加上这两班各自的结果
• 复制数组，合并排序
• 左边比右边大的情况，在统计逆序对

import java.util.*;
public class Solution {
    public int mod = 1000000007;
    public  int mergeSort(int left, int right, int [] data, int [] temp)
    {
        if(left >= right) return 0;
        int mid  = (left + right)/2;
        int res = mergeSort(left,  mid, data, temp) + mergeSort(mid + 1, right, data, temp);
        res %= mod;
        int i = left, j = mid + 1;
        for(int k =left; k <= right; k++) temp[k] = data[k];
        for(int k = left; k <= right; k++){
            if(i == mid + 1) data[k] = temp[j++];
            else if(j ==  right + 1 || temp[i] <= temp[j]) data[k] = temp[i++];
            else{
                data[k] = temp[j ++];
                res += mid - i + 1;
            }
        }
        return res % mod;
    }
    public int InversePairs (int[] nums) {
        int n = nums.length;
        int [] res =  new int[n];
        return mergeSort(0, n-1, nums, res);
    }
}