阅读 32

归并算法经典应用——求解逆序数

本文始发于个人公众号:TechFlow,原创不易,求个关注


在之前介绍线性代数行列式计算公式的时候,我们曾经介绍过逆序数:我们在列举出行列式的每一项之后,需要通过逆序数来确定这一项符号的正负性。如果有忘记的同学可以回到之前的文章当中复习一下:

线性代数行列式

如果忘记呢,问题也不大,这个概念比较简单,我想大家很快就能都搞清楚。

今天的这一篇文章,我想和大家聊聊逆序数的算法,也是一道非常经典的算法题,经常在各大公司的面试题当中出现。

我们先来回顾一下逆序数的定义,所谓逆序数指的是数组当中究竟存在多少组数对,使得排在前面的数大于排在后面的数。我们举个例子,假设当下有一个数组是: [1, 3, 2]。

对于数对(3, 2)来说,由于3排在2前面,并且3 > 2,那么就说明(3, 2)是一对逆序数对。整个数组当中所有逆序数对的个数就是逆序数。

我们从逆序数的定义当中不难发现,逆序数其实是用来衡量一个数组有序程度的一个指标。逆序数越大,说明这个数组递增性越差。如果逆序数为0,说明这个序列是严格递增的。如果一个长度为n的数组的逆序数是C_n^2,那么说明这个数组是严格递减的,此时逆序数最大。

那么,我们怎么快速地求解逆序数呢?


暴力解法


显然,这个问题可以暴力求解,我们只需要遍历所有的数对,然后判断是否构成逆序即可,最后累加一下所有逆序数对的个数就是最终的答案。

这个代码非常简单,只需要几行:

inverse = 0
for i in range(1, 10):
    for j in range(0, i):
        if arr[j] > arr[i]:
            inverse += 1
复制代码

这样当然是可以的,但是我们也很容易发现,这样做的时间复杂度是O(n^2),这在很多时候是我们不能接受的。即使是运行速度非常快的C++,在单核CPU上一秒钟的时间,也就能跑最多n=1000这个规模。再大需要消耗的时间就会陡然增加,而在实际应用当中,一个长度超过1000的数组简直是家常便饭。显然,我们需要优化这个算法,不能简单地暴力求解。


分治


我们可以尝试使用分治算法来解决这个问题。

对于一个数组arr来说,我们试着将它拆分成两半,比如当下arr是[32, 36, 3, 9, 29, 16, 35, 73, 34, 82]。我们拆分成两半之后分别是[32, 36, 3, 9, 29]和[16, 35, 73, 34, 82]。我们令左边半边的子数组是A,右边半边的子数组是B。显然A和B都是原问题的子问题,我们可以假设通过递归可以求解出A和B子问题的结果。

那么问题来了,我们怎么通过A、B子问题的结果来构建arr的结果呢?也就是说,我们怎么通过子问题分治来获取原问题的答案呢?

在回答之前,我们先来分析一下当前的情况。当我们将arr数组拆分成了AB两个部分之后,整个arr的逆序数就变成了三个部分。分别是A数组之间的逆序数、B数组之间的逆序数,以及AB两个数组之间的逆序数,也就是一个元素在A中,一个元素在B中的逆序数对。我们再来分析一下,会发现A数组中的元素交换位置,只会影响A数组之间的逆序数,并不会影响B以及AB之间构成的逆序数。因为A中的元素即使交换位置,也在B数组所有元素之前。


我们举个例子:


假设arr=[3, 5, 1, 4],那么A=[3, 5], B=[1, 4]。对于arr而言,它的逆序数是3分别是(3, 1), (5, 1)和(5, 4)。对于A而言,它的逆序数是0,B的逆序数也是0。我们试着交换一下B当中的位置,交换之后的B=(4, 1),此时arr=[3, 5, 4, 1]。那么B的逆序数变成1,A的逆序数依然还是0。而整体arr的逆序数变成了4,分别是:(3, 1),(5, 1),(5, 4)和(4,1),很明显整体的逆序数新增的就是B交换元素带来的。通过观察,我们也能发现,对于A中的3和5而言,B中的1和4的顺序并不影响它们构成逆序数的数量。

想明白了这一层,剩下的就简单了。既然A和B当中的元素无论怎么交换顺序也不会影响对方的结果,那么我们就可以放心地使用分治算法来解决了。我们先假设,我们可以通过递归获取A和B各自的逆序数。那么剩下的问题就是找出所有A和B个占一个元素的逆序数对的情况了。

我们先对A和B中的元素进行排序,我们之前已经验证过了,我们调整A或者B当中的元素顺序,并不会改变横跨AB逆序数的数量,而我们通过递归已经求到了A和B中各自逆序数对的数量,所以我们存下来之后,就可以对A和B中的元素进行排序了。A和B中元素有序了之后,我们可以用插入排序的方法,将A中的元素依次插入B当中。

B: XXXXXXXXX j XXXXXXXXXXXX
            /
          ai

复制代码

从上图我们可以看出来,假设我们把a_i这个元素插入B数组当中j的位置。由于之前a_i排在B这j个元素之前,所以构成了j个逆序数对。我们对于所有A中的元素a_i求出它在B数组所有插入的位置j,然后对j求和即可。

比较容易想到,由于B元素有序,我们可以通过二分的方法来查找A当中元素的位置。但其实还有更好的办法,我们一个步骤就可以完成AB的排序以及插入,就是将AB两个有序的数组进行归并。在归并的过程当中,我们既可以知道插入的B数组中的位置,又可以完成数组的排序,也就顺带解决了A和B排序的问题。所以整个步骤其实就是归并排序的延伸,虽然整个代码和归并排序差别非常小,但是,这个过程当中的推导和思考非常重要。

如果你能理解上面这些推导过程,我相信代码对你来说并不困难。如果你还没能完全理解,也没有关系,借着代码,我相信你会理解得更轻松。话不多说了,让我们来看代码吧:

def inverse_num(array):
    n = len(array)
    if n <= 1:
        return 0, array

    mid = n // 2
    # 将数组拆分为二往下递归
    inverse_l, arr_l = inverse_num(array[:mid])
    inverse_r, arr_r = inverse_num(array[mid:])

    nl, nr = len(arr_l), len(arr_r)

    # 插入最大的int作为标兵,可以简化判断超界的代码
    arr_l.append(sys.maxsize)
    arr_r.append(sys.maxsize)

    i, j = 0, 0
    new_arr = []
    # 存储array对应的逆序数
    inverse = inverse_l + inverse_r

    while i < nl or j < nr:
        if arr_l[i] <= arr_r[j]:
            # 插入A[i]的时候逆序数增加j
            inverse += j
            new_arr.append(arr_l[i])
            i += 1
        else:
            new_arr.append(arr_r[j])
            j += 1
    return inverse, new_arr
复制代码

从代码层面来看,上面这段代码实现了归并排序的同时也算出了逆序数。所以这就是为什么很多人会将两者相提并论的原因,也是我个人非常喜欢这个问题的原因。看起来完全不相关的两个问题,竟然能用几乎同一套代码来解决,不得不感叹算法的神奇。也正是因此,我们这些算法的研究和学习者,才能获取到源源不断的乐趣。

今天的文章就到这里,如果觉得有所收获,请顺手扫码点个关注吧,你们的支持是我最大的动力。

关注下面的标签,发现更多相似文章
评论