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

开始想到的是用一个二重循环来遍历数组。

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(!data.size()){
            return 0;
        }
        int count = 0;
        for(int i = 0;i < data.size() - 1;i++){
            for(int j = i + 1;j < data.size();j++){
                if(data.at(i) > data.at(j)){
                    count++;
                }
            }
        }
        return count%1000000007;
    }
};

这种做法测试用例全过，但在提交的第五个用例超时。
看来这道题时间卡的比较死，时间复杂度必须满足O(nlogn)才能过。
上面这种写法，虽然用到的二重循环，但每次循环后内循环的长度都减一，所以实际上时间复杂度是小于O(n^2)的，当然还是比O(nlogn)大。而空间复杂度则为O(1)。

在看到要求时间复杂度为O(nlogn)时，正确的想法应该想到快速排序、归并排序、堆排序。而本题更适合用归并排序来解。

下面的代码使用递归的方法实现归并排序，由于归并排序的过程我也掌握的不牢固，所以在核心判断的地方有些注释。

这里有两个坑，第一个是对归并排序的理解不够透彻造成的(说实话现在想的也不是很清晰)。

else if(ir == right + 1 || data.at(il) < data.at(ir))
else if(ir == right + 1 || st.at(il) < st.at(ir))

上面这个判断语句，最开始我写的是上面那种，题目提供的测试用例无事通过，但提交的第一个用例就结果出错，少统计了一些。
观察两个语句的区别，上面的是使用data数组的元素进行比较，而data是在循环中排序的数组。下面的是使用st数组的元素进行比较，即用来储存原始数据的临时数组。这里出错的原因也可以理解，因为每一次循环都会确定data中下标为i的元素的值，而每一次循环中左边数组的下标il与右边数组的下标ir仅有一个会发生改变，若il或ir中其之一与i重合时发生了改变，而恰好这一轮循环并未移动该下标，则发生错误。

举一个简单的例子，{231}。归并发生时首先归并{23}，然后归并{1}，最后对{23}{1}进行归并。在归并{23}{1}时，左指针il指向2，右指针ir指向1，第一轮比较时2>1，将data.at(0)改为右指针指向的1，而此时il的值也为0，这就导致同时il指向的数也变为1，此时原始数组为{131}，归并视野中的左右数组为{13}{}，由于右数组已空，直接按顺序插入左数组，原始数组就会变为{113}，这显然是错误结果，甚至改变了原始数组。所以归并排序时一定要用临时数组的值来进行比较，这也是定义临时数组的作用之一。比较好的办法是在将原始数组赋给临时数组之后，直接将原始数组作为空数组来思考，而将临时数组作为工作数组。

另一个坑是在用例5的时候数组过大导致int型溢出了，这里需要在归并函数中每一次得到count之后都对1000000007进行取模，若只在最后返回结果时取模，会有溢出风险。

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(!data.size()){
            return 0;
        }
        vector<int> st(data.size());
        return merge(data, st, 0, data.size() - 1)%1000000007;
    }
    int merge(vector<int>& data, vector<int>& st, int left, int right){
        if(left >= right){
            return 0;
        }
        int mid = left + (right - left)/2;
        int count = merge(data, st, left, mid) + merge(data, st, mid + 1, right);
        count %= 1000000007;
        int il = left;
        int ir = mid + 1;
        for(int i = left;i <= right;i++){//将经过递归拍好序的数组赋值给临时数组st
            st.at(i) = data.at(i);
        }
        for(int i = left;i <= right;i++){
            if(il == mid + 1){//左边数组已全部归并
                data.at(i) = st.at(ir++);
            }
            else if(ir == right + 1 || st.at(il) < st.at(ir)){//右边数组已全部归并，或左边数组数小于右边数组数
                data.at(i) = st.at(il++);
            }
            else{//左边数组数大于右边数组数，逆序发生，此时左边数组还剩mid - il + 1个数，它们全部与ir数组成逆序对
                data.at(i) = st.at(ir++);
                count = count + mid - il + 1;
            }
        }
        return count;
    }
};