题解 | #数组中的逆序对#

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

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

对于100%的数据,size≤10^5

方法一：暴力求解

求解思路
对于求解逆序对，既可以从数组的第一位开始，依次比较后面的数字与前面数字的大小，并记录其是否构成逆序数。

图片说明

解题代码

class Solution {
private:
    const int mymod = 1000000007;
public:
    int InversePairs(vector<int> data) {
        int count = 0;//记录逆序数的个数
        int n = data.size();
        for (int i = 0; i < n; ++i) //外层循环
        {
            for (int j = i + 1; j < n; ++j) //内层循环
            {
                if (data[i] > data[j]) //判断是否构成逆序数
                {
                    count += 1;
                    count %= mymod;
                }
            }
        }
        return count;
    }
};

复杂度分析
时间复杂度：两层循环， $图片说明$ ,但是运行超时！
空间复杂度：没有引入额外的地址空间，为 $O(1)$

方法二：归并排序的思想

求解思路
对于此题目正好可以采用归并排序的思想，先分后合，在进行合并的同时记录逆序数即可

图片说明

解题代码

public class Solution {
    static int mymod = (int) 1e9 + 7; // 声明常量
    static int mycount = 0;
    static int[] myarr = new int[220000];
    public static void Merge(int l, int mid, int r, int[] array) {
        int i = l, j = mid + 1, k = l;
        while (i <= mid && j <= r) 
        {
            if (array[i] <= array[j]) // 对数组进行判断
            {
                myarr[k++] = array[i++];
            } 
            else 
            {
                mycount = (mycount + mid - i + 1) % mymod; // 开始计数，在这里直接模1000000007即可
                myarr[k++] = array[j++];
            }
        }
        while (i <= mid) // 重新构造数组
        {
            myarr[k++] = array[i++];
        }
        while (j <= r) // 重新构造数组
        {
            myarr[k++] = array[j++];
        }
        for (i = l; i <= r; i++) 
        {
            array[i] = myarr[i];
        }
    }
    //归并排序模板
    public static void MergeSort(int l, int r, int[] array) 
    {
        if (l < r) 
        {
            int mid = (l + r) >> 1;
            MergeSort(l, mid, array); // 递归的思想来归并排序
            MergeSort(mid + 1, r, array); // 递归的思想来归并排序
            Merge(l, mid, r, array);
        }
    }
    public static int InversePairs(int[] myarray) // 求解逆序数
    {
        if (myarray == null || myarray.length == 0) 
        {
            return 0;
        }
        MergeSort(0, myarray.length - 1, myarray);
        return mycount;//返回结果即可
    }
}

复杂度分析
时间复杂度：归并排序的时间复杂度，为 $O(nlogn)$
空间复杂度：引入一个新的数组，空间复杂度为 $O(N)$