要么改变世界,要么适应世界

基于分治法的特定数列逆序数求法

2022-09-30 09:25:57
61
目录

忙里偷闲,记录一下使用分治法求逆序数的实现过程。

算法设计

**逆序:**在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。例如<3,1>就是一个逆序。

**逆序数:**给定数列中,逆序的数目。例如数列:

[1,3,4,2]

逆序数是2.

暴力法

很容易就想到的一个方法就是从头开始扫描,然后对于每一个扫描到的数字a,考察后面的每一个数字b,观察其是否满足逆序的定义,例如对于上述数列,对于数字1,逆序数为0;对于数字3,逆序数为1(<3,2>),依此类推,最终数列总的逆序数为2.

很遗憾,该算法复杂度为$O(n^2)$,对于暴躁的张三来说,当其要计算长度为10000的数列的逆序数时候,他是无法接受长时间等待的,因为他还要去和阿珍约会呢

分治法

分而治之,逐个击破

分治法的思想是将原问题分解成若干个子问题,而所有的子问题进行简单处理后就可以得到原问题的解。求解子问题的过程亦可以继续分解成子子问题,而子问题分解到“原子问题”(原子问题好像也不太严谨,大概意思就是一个可以直接求解的问题)后可以立即得到解。

例如对于下面的数列:我们可以每次把子数列分成两半,分别求左半部分和右半部分的逆序数

image-20220929225648745

那我们如何还原出原问题的解呢?即未分解问题时候的逆序数。仔细想想,我们已经计算出了左右两边逆序数leftCntrightCnt,那么我们再计算出在“ 一个数字取自左边,另一个数字取自右边”的情况下,逆序数cnt的大小,原问题不就是这三个数字之和吗?

关键是怎么求cnt?

老方法?依次从左边选一个数字a,再依次从右边选一个数字b,很抱歉,这样子下来要判断$\frac{n}{2}*\frac{n}{2}=\frac{n^2}{4} $次,综合下来时间复杂度还是$O(n^2)$。

仔细想想,我们要判断的数字一个来自左边,一个来自右边,如果我们分别让左边和右边有序,然后分别从第一个开始遍历,根据遍历到的数字进行计算逆序数,根据有序的性质,遍历完后逆序数也求解出来了,整个过程中,排序花费$O(n\log n)$,遍历花费$O(n)$,即合并子问题花费$O(n\log n)$.

关于合并过程的仔细分析,如下(简单起见,数列中不包含相同元素):

先将左右两部分排序,设置两个指针,分别从左右两部分进行遍历,设左边遍历得到的数字是a[i],右边的是b[j]

  1. 右边的指针j不断往后移动(尚未到结尾,如果到结尾,则到步骤3),直到b[j]恰好是右半部分中第一个不小于a[i]的数字,即在右半部分中b[j]的左边都是小于a[i]的,此时,由a[i]作为第一个数字组成的跨越左右两部分的数对(或者说序偶)中,逆序数刚好就是右半部分中b[j]的左边的数字个数。说起来有点绕口,看看下面的图:

image-20220930001126349

此时逆序数cnt要加上n.

  1. 左边的指针要往后移动,即指向a[i+1],那么就会有两种情况:
  • a[i+1]>b[j]:这个很好解决,继续回到步骤1即可。
  • a[i+1]<b[j]:由于b[j]的左边都是小于a[i],即存在这样的关系:b[j]>a[i+1]>a[i]>b[j-1],故此时由a[i+1]作为第一个数字组成的跨越左右两部分的数对(或者说序偶)中,逆序数也是n,此时逆序数cnt要加上n.下一步左边的指针要往后移动,继续步骤②,直到左边的指针指向元素比右边指针指向的大,回到步骤1,假若左边的指针先到了左半部分的最右边,则到步骤3。
  1. 此时要么左半部分先遍历完,要么右半部分先遍历完,假如是左边先遍历完,则说明此时“跨越左右两半部分的逆序数”统计完成,即cnt是正确的值,跳步骤4.如果是右半部分先遍历完成,则说明左边尚未遍历完成的数字都要比右半部分的数字大,根据这个条件计算逆序数后,转步骤4.
  2. leftCnt + rightCnt + cnt作为原问题的解。

算法分析

下面进行时间复杂度分析,我们子问题个数是2(分别递归求解左右两个部分),每个子问题的规模是原来的一半,合并子问题花费$O(n\log n)$。

则: $$ T(n)=2T(\frac{n}{2} )+O(n \log n) $$ 根据主定理,得 $$ T(n)=O(n \log n) $$

算法实现

#include<iostream>
#include<algorithm>
using namespace std;
const int LEN = 100000 + 2;
int list[LEN], length;
long long reverseOrderNumber(int left, int right){
    if (left >= right)return 0;
    if (left + 1 == right)return list[left] > list[right];
    int mid = (left + right) >> 1;
    // 分别求解子问题
    long long leftCnt  = reverseOrderNumber(left, mid);
    long long rightCnt = reverseOrderNumber(mid + 1, right);
    // 排序左右两半部分
    int *l1 = list + left, *r1 = list + mid - left + 1 + left;
    sort(l1, r1);
    sort(r1, list + right + 1);
    // 计算跨左右部分的逆序数
    int i = left, j = mid + 1;
    long long cnt = 0;
    while(i <= mid && j <= right){
        // 在右边寻找第一个大于 a[i] 的元素
        while(j <= right && list[i] > list[j])j++;
        if (j > right)break;
        while(i <= mid && list[i] < list[j]){
            i++;
            cnt += j - 1 - mid;
        }
    }
    // 左边尚未遍历完的数字都要比右半部分的大
    if(j > right) cnt += (mid - i + 1) * (right - mid);
    // 合并子问题
    return leftCnt + rightCnt + cnt;
}
int main(){
    // printf("input the length:\n");
    scanf("%d", &length);
    // printf("input the value:\n");
    for (int i = 0; i < length;i++)
        scanf("%d", &list[i]);
    printf("%lld\n", reverseOrderNumber(0, length - 1));
    return 0;
}
/*

4
5 3 7 2

4
5 9 7 2

8
5 9 12 16 2 3 13 14

3
7 4 3

6
2 6 3 4 5 1

*/

实际上排序过程也可以使用归并排序,并且排序过程就可以计算逆序数了,不过归并排序过程要辅助空间,这里就没有采用。

历史评论
开始评论