493. Reverse Pairs.md

493. Reverse Pairs

思路

求（重要）逆序对数。虽然求的不是普通的逆序对而是i < j && nums[i] > 2*nums[j]，但解法几乎都是一样的。我们甚至可以把逆序对定义成i < j && nums[i] > f(nums[j])。

思路一、归并排序

此题最经典的解法就是类似归并排序的分治法。即我们不断将大问题划分成两个子问题最后再合并起来，用式子表示就是T(i, j) = T(i, m) + T(m+1, j) + C, m = (i+j)/2。这里的C就是合并两个子问题，即“已知逆序对的两个数字分别位于子数组 nums[i, m] 和 nums[m+1, j] 之中，求满足这个条件的逆序对个数”。暴力求C的思路是用个两层循环遍历两个子数组，复杂度为平方级别，不可取。所以我们可以先对两个子数组排序，这样再用两个指针即可在线性复杂度内求得C。还需要解决最后一个问题，那就是如何对数组进行排序，我们当然可以直接调用STL中的sort，但是更快的方法是采用归并排序的思想里面的merge操作，因为不要忘了待排序数组的前后两半都是排好序的，这样我们每次排序的复杂度就是线性的。

关于merge操作，这里多少几句，STL中有两个相关函数：

1. merge: 将两个的有序的序列(两个序列可以在同一容器内)归并到另一个容器中；
   • 例：merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin())
2. inplace_merge: 将一个容器内分两个有序的部分归并到本身的容器。
   • 例：inplace_merge(vec1.begin(), vec1.begin() + mid + 1, vec1.end(), cmp)（第二个参数是后半部分的开始，即mid+1；另外可传入比较函数，默认less<int>()）

inplace_merge的基本思想就是开辟额外的空间，然后再归并到本身的容器里，我们也可以自己实现这个函数（亲测会快一些），见代码中的my_merge。

时间复杂度O(nlogn)，空间复杂度O(n)

思路二

根据用户fun4LeetCode在评论区的帖子，除了思路一之外，还有另外一种思路。

根据这个帖子，作者说这类问题的核心就是将大问题划分成小问题求解，并总结了两个常用的划分方式：

1. Sequential recurrence relation：即T(i, j) = T(i, j - 1) + C，C代表最后一个元素与前面所有元素的合并。
2. Partition recurrence relation：即T(i, j) = T(i, m) + T(m + 1, j) + C, m = (i+j)/2，C代表前后两个部分的合并。

即思路一使用的就是Partition recurrence relation，其实还可以使用Sequential recurrence relation。

为了求得此时的C（求最后一个元素与其他元素之间构成的逆序对数），暴力的思路就是挨个比较最后一个元素与其他所有元素的大小关系，但更快的思路是使用插入和搜索都很快的数据结构，例如平衡二叉搜索树、线段数组（binary indexed tree）和线段树等，详情请参考原贴。

这个帖子总结得非常好，先挖个坑，有空了再仔细学习学习。

C++

思路一

class Solution {
private:
    vector<int>nums_bk = vector<int>(50000);
    void my_merge(vector<int>& nums, int l, int mid, int r){
        /*手动实现inplce_merge, 要求nums[l~mid]和nums[mid+1~r]是已有序的*/
        if(l == r) return;
        for(int i = l; i <= r; i++) nums_bk[i] = nums[i];
        
        int i = l, j = mid + 1, idx = l;
        while(i <= mid && j <= r){
            if(nums_bk[i] <= nums_bk[j]) nums[idx++] = nums_bk[i++];
            else nums[idx++] = nums_bk[j++];
        }
        while(i <= mid) nums[idx++] = nums_bk[i++];
        while(j <= r) nums[idx++] = nums_bk[j++];
    }
    
    int mergeSort(vector<int>& nums, int l, int r){
        if(l >= r) return 0;
        
        // 1. divide
        int mid = (l + r) / 2, i = l, j = mid + 1;
        int res = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);     
        // 此时前后两半都是各自有序的   
        
        // 2. conquer
        while(i <= mid && j <= r){
            if(nums[i] <= (long long)nums[j] * 2) i++;
            else{
                res +=  (mid - i + 1); 
                j++;
            }
        }
        // sort(nums.begin() + l, nums.begin() + r + 1); // 无脑排序也可以只是复杂度为O(nlogn)
        my_merge(nums, l, mid, r); // O(n)
        // inplace_merge(nums.begin() + l, nums.begin() + mid + 1, \
        //               nums.begin() + r + 1, less<int>()); // O(n)
        return res;
    }
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
};