题目

题解

三个方法

1. 暴力法

必超时，挨个比较每两个数

  • 时间复杂度$O(n^{2})$
  • 空间复杂度$O(1)$

2. 归并排序法

就是用归并排序的思想，在归并排序中添加两行代码，具体分析可见官方题解

  • 时间复杂度$O(nlog{n})$
  • 空间复杂度$O(n)$
class Solution {//两个方法。1.归并排序法（递归）
    //与归并排序有两处不同
    int res = 0;//定义res存逆序数对的个数
public:
    void merge(vector<int> &a, vector<int> &b, int start1, int end1, int start2, int end2){
        int b_start = start1;//这个变量作为两个数组合并时新数组的指针
        int cur_start1 = start1, cur_start2 = start2;//定义两个指针指向两数组当前值
        while(cur_start1<=end1 && cur_start2<=end2){
            //不同1！当1数组的数字并入，res加上2数组当前指针和开始指针的差值。即当前指针之前的数均小于1数组当前加入的数
            //注意！这里要用<=，否则第二处不同会把相等的数字也算作逆序
            res += a[cur_start1]<=a[cur_start2]? cur_start2-start2 : 0;
            //归并中的合并，哪个小取哪个
            b[b_start++] = a[cur_start1]<=a[cur_start2]? a[cur_start1++] : a[cur_start2++];
        }
        while(cur_start1<=end1){
            //不同2！1数组有剩下的部分也要加上2数组当前指针和开始指针的差值，和不同1的原理一样
            b[b_start++] = a[cur_start1++];
            res += cur_start2-start2;
        }
        while(cur_start2<=end2) b[b_start++] = a[cur_start2++];

        for(int i=start1; i<=end2; ++i){
            a[i] = b[i];
        }
    }
    void mergeSort(vector<int> &a, vector<int> &b, int start, int end){
        if(start>=end) return;
        int mid = start + (end-start)/2;
        int start1 = start, end1 = mid;
        int start2 = mid+1, end2 = end;//定义两个数组的开头结尾

        //递归分割左右两个数组
        mergeSort(a, b, start1, end1);
        mergeSort(a, b, start2, end2);
        //将左右两个数组合并
        merge(a, b, start1, end1, start2, end2);
    }

    int reversePairs(vector<int>& nums) {
        const int n = nums.size();
        vector<int> help_nums(n);
        mergeSort(nums, help_nums, 0, n-1);//进行归并排序
        return res;
    }
};

3. 归并排序法

也是用归并排序的思想，在归并排序中添加两行代码，具体分析可见官方题解
和方法2的差别就是不进行递归了

  • 时间复杂度$O(nlog{n})$
  • 空间复杂度$O(n)$
class Solution {//两个方法。2.归并排序法（非递归）
    //与归并排序有两处不同
    int res = 0;//定义res存逆序数对的个数
public:
    void merge(vector<int> &a, vector<int> &b, int start1, int end1, int start2, int end2){
        int b_start = start1;//这个变量作为两个数组合并时新数组的指针
        int cur_start1 = start1, cur_start2 = start2;//定义两个指针指向两数组当前值
        while(cur_start1<=end1 && cur_start2<=end2){
            //不同1！当1数组的数字并入，res加上2数组当前指针和开始指针的差值。即当前指针之前的数均小于1数组当前加入的数
            //注意！这里要用<=，否则第二处不同会把相等的数字也算作逆序
            res += a[cur_start1]<=a[cur_start2]? cur_start2-start2 : 0;
            //归并中的合并，哪个小取哪个
            b[b_start++] = a[cur_start1]<=a[cur_start2]? a[cur_start1++] : a[cur_start2++];
        }
        while(cur_start1<=end1){
            //不同2！1数组有剩下的部分也要加上2数组当前指针和开始指针的差值，和不同1的原理一样
            b[b_start++] = a[cur_start1++];
            res += cur_start2-start2;
        }
        while(cur_start2<=end2) b[b_start++] = a[cur_start2++];

        for(int i=start1; i<=end2; ++i){
            a[i] = b[i];
        }
    }
    void mergeSort(vector<int> &a, vector<int> &b, int start, int end){
        const int n = end-start+1;//n是数组的长度
        //从下向上，先1个1个，再2个2个，最后到stride为n，进行归并
        for(int stride =1; stride <= n; stride*=2){
            int i = start;//从start开始
            //按stride为步长进行两两归并，当数组剩下的数少于2*stride时停止
            for(; i<=end-2*stride+1; i+=2*stride){
                merge(a, b, i, i+stride-1, i+stride, i+2*stride-1);
            }
            //看剩下的数够不够1个stride，够的话就再归并一次，即使两个数组长度可能不一样
            if(i < end-stride+1){
                merge(a, b, i, i+stride-1, i+stride, end);
            }
        }
    }

    int reversePairs(vector<int>& nums) {
        const int n = nums.size();
        vector<int> help_nums(n);
        mergeSort(nums, help_nums, 0, n-1);//进行归并排序
        return res;
    }
};

4. 离散化数组

这个方法还没有弄明白，以后有时间再看