「LeetCode」逆序对

2020-04-15
摘要: 简单介绍逆序对的求法以及应用。

##定义
一个数对 $(i,j)$,如果 $i>j$,则这个数对就是一个逆序对。

例如:数组 $[2,3,8,6,1]$ 中的逆序对为:$(2,1)$, $(3,1)$, $(8,1)$, $(8,6)$, $(6,1)$ ,共 $5$ 个逆序对。

求逆序对的方法#

目前求逆序对数目比较普遍的方法是利用归并排序做到 $O(n\log(n))$ 的时间复杂度。当然,也可以利用树状数组(代码量更少,也可以解决动态区间的逆序对问题。详见超链接)、线段树来实现这种基础功能,复杂度也为 $O(n\log(n))$。

借用 @seniusen 的图:

我们在每次合并子数组的时候比较两个子数组来得到逆序对,完成所有合并即可得到所有的逆序对。比如,我们在合并 $[11],[8]$ 时得到了一个逆序对 $(11,8)$;我们在合并 $[8,11],[3,9]$ 的时候得到了逆序对 $(8,3), (11,3), (11,9)$。

主要代码如下

while(p < r) {
    while(pl < mid && pr == r)...
    while(pl == mid && pr < r)...
    while(pl < mid && pr < r && nums[pl] <= nums[pr]) {
          temp[p++] = nums[pl++];
    }
    while(pl < mid && pr < r && nums[pl] > nums[pr]) {
        ans += mid - pl;
        temp[p++] = nums[pr++];
    }
}

我们在每次合并的时候,如果发现 nums[pl] > nums[pr],说明 plmid 的数都比 nums[pr] 大,即有 $\mathrm{mid-pl}$ 个逆序对。但是千万要注意,在相等的情况下,我们应该使用 pl++,也就是取左侧的那个数,否则会遗漏逆序对的个数,如下所示:
$$\mathrm{L}:\underline{3},4,8,9$$
$$\mathrm{R}:1,\underline{3},5,7$$
当我们比较到两个 $3$ 时,如果取的是右侧的 $3$,那么逆序对 $(4,3),(8,3),(9,3)$ 便被遗漏;如果取左侧的 $3$,遗漏的 $(3,5),(3,7)$ 都不是逆序对(若求顺序对则相反,参见 逆序对 - 腾讯 2020 后台校园招聘试题)。

这种算法的充分性显而易见,那么必要性呢?为什么这样操作可以得到所有的逆序对?实际上我们模拟这个过程,可以发现针对每个数,将其作为 $i$(较大的数),与其后的所有数都进行了一次对比,因此,我们没有遗漏地进行了所有的查找,而只用到了 $O(n\log(n))$ 的时间复杂度。

求顺序对#

注意修改的部分,>=, pr++, pl++, r - pr

while(p < r) {
    while(pl < mid && pr == r)...
    while(pl == mid && pr < r)...
    while(pl < mid && pr < r && nums[pl] >= nums[pr]) {
          tmp[p++] = nums[pr++];
    }
      while(pl < mid && pr < r && nums[pl] < nums[pr]) {
                ans += r - pr;
            tmp[p++] = nums[pl++];
  }
}

同时求逆序对和顺序对#

无法做到.. 比如说下面这段代码是错的:

while(p < r) {
    while(pl < mid && pr == r)...
    while(pl == mid && pr < r)...
    while(pl < mid && pr < r && nums[pl] < nums[pr]) {
        order[index] += r - pr;
        tmp[p++] = nums[pl++];
    }
    while(pl < mid && pr < r && nums[pl] > nums[pr]) {
          inversion[index] += mid - pl;
          tmp[p++] = nums[pr++];
        }
    while(pl < mid && pr < r && nums[pl] == nums[pr]) {
          tmp[p++] = nums[pl++]; // pl++? pr++?
    }
}

因为求顺序对和逆序对时,处理相等的情况采取的策略是冲突的,因此无法同时完成。具体参考上文说明。

例题#

LeetCode 面试题51. 数组中的逆序对#

LeetCode 面试题51. 数组中的逆序对

这题就是单纯地求逆序对的个数。

class Solution {
public:
    /*
        [l,r)
    */
    int ans = 0;
    void mergeSort(vector<int>& nums, vector<int>& temp, int l, int r) {
        if(l+1 == r) return;

        int mid = (l+r)/2;
        mergeSort(nums, temp, l, mid);
        mergeSort(nums, temp, mid, r);

        int pl = l, pr = mid, p = l;
        while(p < r) {
            while(pl < mid && pr == r) {
                temp[p++] = nums[pl++];
            }
            while(pl == mid && pr < r) {
                temp[p++] = nums[pr++];
            }
            while(pl < mid && pr < r && nums[pl] <= nums[pr]) {
                temp[p++] = nums[pl++];
            }
            while(pl < mid && pr < r && nums[pl] > nums[pr]) {
                ans += mid - pl;
                temp[p++] = nums[pr++];
            }
        }

        for(int i = l; i < r; ++i) {
            nums[i] = temp[i];
        }
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> temp(n, 0);
        mergeSort(nums, temp, 0, n);
        
        return ans;
    }
};

逆序对 - 腾讯 2020 后台校园招聘试题#

逆序对 - 腾讯 2020 后台校园招聘试题

这题稍微复杂一些。我们需要计算出每次以 $2^{q_i}$ 个数为一组进行翻转后整个数组的逆序对的个数。观察题目要求,数字的个数是 $2^n$ 个,那么每次就有 $2^{n-q_i}$ 组数字被翻转。如图所示,每次翻转数据都是严格地平均分组的,$2^0$ 一组,$2^1$ 一组….

再仔细观察,若翻转以 $2^i$ 个数为一组,实际上等价于分别以 $2^1,\cdots,2^{i-1}$ 个数为一组进行左右交换。如图所示为 $n=3,i=3$ 的情况。

我们接下来定义 $\mathrm{inversion}[i]$ 。将数组分为每 $2^{i+1}$ 个数一组,左边 $2^i$ 个数与右边 $2^i$ 个数之间的逆序数对之和即为 $\mathrm{inversion}[i]$。于是 $\mathrm{inversion}[i]$ 就可以在归并排序合并 $2^{i}+2^{i}$ 个数时得到。

我们接下来再定义 $\mathrm{order}[i]$ 。将数组分为每 $2^{i+1}$ 个数一组,左边 $2^i$ 个数与右边 $2^i$ 个数之间的顺序数对之和即为 $\mathrm{order}[i]$。于是 $\mathrm{order}[i]$ 可以在归并排序合并 $2^{i}+2^{i}$ 个数时得到。

结合翻转过程,我们可以给出以下论述:

因为每次以 $2^{q_i}$ 个数为一组进行翻转时,实际上等价于分别以 $2^1,\cdots,2^{i-1}$ 个数为一组进行左右交换。其中以 $2^i$ 个数为一组进行左右交换时,$\mathrm{inversion}[i-1]$ 的值和 $\mathrm{order}[i-1]$ 进行了交换(因为翻转后顺序对个数和逆序对个数交换),其他值不变(相对位置不变)。因此我们只需要针对 $k\in[1,i-1]$, $\mathrm{swap(inversion[}k-1\mathrm{], order[}k-1])$ 即可得到实时的顺序对、逆序对记录。而结合归并排序求逆序对的过程,$\mathrm{inversion}$ 数组和 $\mathrm{order}$ 求和便是整个数组的逆序对个数、顺序对个数,于是我们只需要维护这两个数组就可以得到每次翻转的逆序对个数。

就像之前说的,$\mathrm{inversion}$ 和 $\mathrm{order}$ 可以在归并排序的过程中得到。注意,我们不能够同时得到逆序对和顺序对的个数(参见上文)。我们采用将原数组进行 reverse 操作,再计算逆序对的个数(即顺序对的个数)。由于存在相等的情况,因此也不能通过总数对减去逆序对个数的方法来求顺序对个数。

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

void mergeSort(vector<long long>& nums, long long l, long long r, vector<long long>& tmp, long long index, vector<long long>& cnt) {
    if(l+1==r) return;
    
    long long mid = (l+r)/2;
    mergeSort(nums, l, mid, tmp, index-1, cnt);
    mergeSort(nums, mid, r, tmp, index-1, cnt);
    
    long long pl = l, pr = mid, p = l;
    while(p < r) {
        while(pl < mid && pr == r) {
            tmp[p++] = nums[pl++];
        }
        while (pl == mid && pr < r) {
            tmp[p++] = nums[pr++];
        }
        while(pl < mid && pr < r && nums[pl] <= nums[pr]) {
            tmp[p++] = nums[pl++];
        }
        while(pl < mid && pr < r && nums[pl] > nums[pr]) {
            cnt[index] += mid - pl;
            tmp[p++] = nums[pr++];
        }
    }
    
    for(long long i = l; i < r; ++i) {
        nums[i] = tmp[i];
    }
}

int main() {
    ios::sync_with_stdio(false);
    
    long long n;
    cin >> n;
    long long nn = pow(2,n);
    vector<long long> nums(nn, 0);
    
    for(long long i = 0; i < nn; ++i) {
        cin >> nums[i];
    }
    
    vector<long long> inversion(n, 0);
    vector<long long> order(n, 0);
    vector<long long> tmp(nn, 0);
    vector<long long> reversedNums(nums.rbegin(), nums.rend());
    mergeSort(nums, 0, nn, tmp, n-1, inversion); // 合并 2^n 个数时,记录的是 inversion[n-1]
    mergeSort(reversedNums, 0, nn, tmp, n-1, order); // 合并 2^n 个数时,记录的是 order[n-1]
    
    long long count;
    cin >> count;
    while(count--) {
        long long m;
        cin >> m;
        for(long long i = 0; i < m; ++i) {
            swap(order[i], inversion[i]);
        }
        
        long long sum = 0;
        for(long long i = 0; i < n; ++i) {
            sum += inversion[i];
        }
        cout << sum << endl;
    }
}