788. 逆序对的数量

首先我们先搞清楚逆序对的含义：对于数列中的第i个和第j个元素，如果满足i < j 且 a[i] < a[j]，则称其为一个逆序对。

然后开始分析问题，此题可以用分治法解决。

将序列从中间进行分开，构成逆序对的两个元素可以分为以下几种情况：

• 两个元素都在左边
• 两个元素都在右边
• 一个在左，一个在右

最关键的便是最后一种情况，前两种通过递归可以化成最后一种~

算法步骤为：

• 递归左边的
• 递归右边的
• 计算一个在左，一个在右的
• 把以上三种加到一块

两个序列中的逆序对如何计算呢？

① 方法一：如果我们采用暴力的写法，那么时间复杂度为O（N^2）, 双层for直接比较然后符合的res++; 容易TLE

② 方法二：设序列为S，第一个序列上的某个元素为i，第二个序列上的元素为j。那么逆序对的数量 Sum(Si), i: l ~ mid. 或 Sum(Sj), j : mid + 1 ~ r

经过观察可以得知，当q[i] > q[j] 时，i ~ mid 的元素都满足 q[i] > q[j]。如此我们便可以算的出 j 对应的逆序对个数: mid - i + 1 。这样的话，我们只需要采用双指针的形式，每次遇到 q[i] > q[j] ，那么Sj就知道了，然后当任意一个序列遍历完，那么逆序对Sum(Sj)也就计算完了。此方法时间复杂度为O（N）。

另外，因为数据最坏情况：n, n-1, n-2 … 1 。可以形成 n-1, n-2, … 1 ，共n*(n-1) / 2个逆序对，n最大10^5^，所以最多有5 * 10^9^ 个，所以应该用Long Long保存返回的结果哦~

代码如下：

#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n, q[N], tmp[N];

LL merge_sort(int q[], int l, int r){
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else{
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 0;i < n; i++) scanf("%d", &q[i]);
    LL res = merge_sort(q, 0, n - 1);
    printf("%lld", res);
    return 0;
}

LeetCode 493. 翻转对

这个题和上面是类似的，关键点在于 合并和计算要分开。

==为啥不能也将 计算逆序对 放在合并的else中呢？==

原因：q[i] > q[j] 时，此时满足逆序对。假如此时不满足本题的翻转对，就会导致 j 元素已经被加入到 tmp数组了，之后就无法和别的 i构成翻转对了。所以要先 计算翻转对（仍是双指针的方法哦，暴力会TLE），再合并。

总结：以后只要遇到 计算逆序对相似的类型题，都可以采用 归并排序 的思想

const int N = 1e5 + 10;
int tmp[N];
class Solution {
public:
int merge_sort(vector<int>& nums, int l, int r) {
    if(l >= r) return 0;
    int mid = l + r >> 1;
    int res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    // O(N^2) TLE
    // for(; i <= mid; i++){
    //  for(j = mid + 1; j <= r; j++){
    //          if((long)nums[i] > (long)2 * nums[j]) res++;
    //  }
    // }
    // 双指针法：O(N)
    while(i <= mid && j <= r){
        if((long)nums[i] > (long)2 * nums[j]) {
            res += mid - i + 1;
            j++;
        }else{
            i++;
        }
    }
    i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if(nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while(i <= mid) tmp[k++] = nums[i++];
    while(j <= r) tmp[k++] = nums[j++];
    for(i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
    return res;
}
int reversePairs(vector<int>& nums) {
    return merge_sort(nums, 0, nums.size() - 1);
}
};