数组中的逆序对

借助归并排序分治问题，在合并解的阶段计数。

归并排序每次将数据分解为nums[p…q]和[q+1…r]，分别求解子问题，然后合并。
在合并的过程中可以完成对逆序对的计数，合并过程逐个从左右区间未选取的元素中选取最小的元素放入结果。
我们可以想到：

• 由于子问题求解完毕后左、右子区间[p…q]、[q+1…r]有序，任意剩余子区间[p+i…q]、[q+1+j…r]也必然有序，所以拿取的最小元素必然是其中一个剩余区间的第一个元素
• 若元素是从左区间拿取，由于它是最小且在所有左侧、右侧剩余元素的最前，所以与该元素不存在相关的逆序对
• 若元素是从右区间拿取，由于它是最小且在所有右侧剩余元素的最前，所以左侧剩余元素nums[q+1+j]与右侧第一个剩余元素nums[q+1+j]构成全部相关的逆序对

class Solution {
public:
    inline int merge(vector<int>& nums, size_t p, size_t q, size_t r) {
        if(!(p<=q && q<r)) return 0;
        int numRev=0;
        size_t n1 = q-p+1, n2 = r-q;
        vector<int> A(n1), B(n2);
        for(size_t i=0;i<n1;i++) A[i]=nums[p+i];
        for(size_t i=0;i<n2;i++) B[i]=nums[q+1+i];
        size_t i=0, j=0;
        for(size_t c=p;c<=r;c++) {
            // 注意判定边界。
            // 另外不可以用哨兵值的方法，因为此题输入可能会包含int的最大值
            if (i>=n1) {
                // 左区间全部用完了，复制右区间
                nums[c] = B[j++];
                // 此处也不需要增加numRev，左侧已经用完，没有元素再与右侧构成逆序对，numRev增量必然是0
            } else if (j>=n2) {
                // 右区间全部用完了，复制左区间
                nums[c] = A[i++];
            } else {
                // 都没用完，正常对比
                if(A[i] <= B[j]) {
                    nums[c] = A[i++];
                } else {
                    nums[c] = B[j++];
                    //if (A[i] != B[j])
                    numRev += n1-i; // 左侧全部剩余元素A[i...n1]与右侧第一个剩余元素B[j]构成全部相关的逆序对
                }
            }
        }
        return numRev;
    }
    int solve(vector<int>& nums, int p, int r){
        if(p>=r) return 0;
        int q=(p+r)/2;
        int cnt=0;
        cnt+=solve(nums,p,q);   // 不要忘记加上子问题时发现的逆序对
        cnt+=solve(nums,q+1,r); // 不要忘记加上子问题时发现的逆序对
        cnt+=merge(nums,p,q,r); // 合并同时也求解本层上的逆序对
        return cnt;
    }
    int reversePairs(vector<int>& nums) {
        vector<int> copy(nums);
        return solve(copy, 0, nums.size()-1);
    }
};

另外在算法导论（第3版第2章思考题2-4.d.）或部分题解上，在merge过程中可能使用了一个极大数作为哨兵值来判断是否其中一个区间已经消耗完毕。

然而，由于题目没有说明数据范围的情况下，我们必须假设输入是全范围的，
也就是说输入可能包括int的最大值2147483647（实际上leetcode上此题测试用例确实包含这个）

因此不可以用大数作为哨兵值的方法

（虽然发现有时测试数据不够强也可能萌混过关）

剑指 Offer 5

Donate