[剑指 Offer 第 2 版第 51 题] “数组中的逆序对”做题记录

第 51 题：数组中的逆序对

传送门：数组中的逆序对，牛客网 online judge 地址。

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

样例：

输入：[1,2,3,4,5,6,0]

输出：6

专门整理成文章。1、用归并排序；2、用 BST。如何记录左子树中结点的个数。

思路1：首先我们应该想到，使用定义计算逆序数。不过时间复杂度是：O(n^2)。

  class Solution(object):
        def inversePairs(self, nums):
            l = len(nums)
            if l < 2:
                return 0
            res = 0
            for i in range(0, l - 1):
                for j in range(i + 1, l):
                    if nums[i] > nums[j]:
                        res += 1
            return res

这种思路虽然很直接，但编写出错的概率就很低了，在没有在线评测系统的时候，它可以作为一个“正确的”参考答案，用以检验我们自己编写的算法是否正确。

思路2：借助归并排序的分治思想，时间复杂度为 O(n \\log n)。

分析：例如：前有序数组：[2,3,5,8]，后有序数组：[4,6,7,12]。

做归并的时候，步骤如下：

第 1 步，2 先出列，2 比“后有序数组”中所有的元素都小，构成“顺序对”；

第 2 步，3 出列，3 比“后有序数组”中所有的元素都小，构成“顺序对”；

第 3 步，4 出列，关键的地方在这里，“前有序数组”中所有剩下的元素 [5,8] 比 4 都大，构成 2 个 “逆序对”；

第 4 步，5 出列，5 比“后有序数组”中所有剩下的元素都小，构成“顺序对”；

第 5 步，6 出列，“前有序数组”中所有剩下的元素 [8] 比 6 都大，构成 1 个“逆序对”；

第 6 步，7 出列，“前有序数组”中所有剩下的元素 [8] 比 7 都大，构成 1 个“逆序对”；

第 7 步，8 出列，8 比“后有序数组”中所有剩下的元素 [8] 都小，构成 1 个“顺序对”；

第 8 步，12 出列，此时“前有序数组”为空。

因此，我们只需要在“前有序数组”非空，且“后有序数组”中有元素出列的时候，即上面的第 3、5、6 步计算“逆序对”就可以了。

参考代码：

  class Solution(object):
        def inversePairs1(self, nums):
            l = len(nums)
            if l < 2:
                return 0
            res = 0
            for i in range(0, l - 1):
                for j in range(i + 1, l):
                    if nums[i] > nums[j]:
                        res += 1
            return res

        def inversePairs(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """

            l = len(nums)
            if l < 2:
                return 0
            temp = [0 for _ in range(l)]
            return self.count_inversion_pairs(nums, 0, l - 1, temp)

        def count_inversion_pairs(self, nums, l, r, temp):
            """
            在数组 nums 的区间 [l,r] 统计逆序对
            :param nums:
            :param l: 待统计数组的左边界，可以取到
            :param r: 待统计数组的右边界，可以取到
            :param temp:
            :return:
            """
            # 极端情况下，就是只有 1 个元素的时候
            if l == r:
                return 0
            mid = l + (r - l) // 2
            left_pairs = self.count_inversion_pairs(nums, l, mid, temp)
            right_pairs = self.count_inversion_pairs(nums, mid + 1, r, temp)

            merge_pairs = 0
            # 代码走到这里的时候，
            # [l, mid] 已经完成了排序并且计算好逆序对
            # [mid + 1, r] 已经完成了排序并且计算好逆序对
            # 如果 nums[mid] <= nums[mid + 1]，此时就不存在逆序对
            # 当 nums[mid] > nums[mid + 1] 的时候，就要继续计算逆序对
            if nums[mid] > nums[mid + 1]:
                # 在归并的过程中计算逆序对
                merge_pairs = self.merge_and_count(nums, l, mid, r, temp)
            # 走到这里有 nums[mid] <= nums[mid + 1] 成立，已经是顺序结构
            return left_pairs + right_pairs + merge_pairs

        def merge_and_count(self, nums, l, mid, r, temp):
            """
            前：[2,3,5,8]，后：[4,6,7,12]
            我们只需要在后面数组元素出列的时候，数一数前面这个数组还剩下多少个数字，
            因为"前"数组和"后"数组都有序，
            因此，"前"数组剩下的元素个数 mid - i + 1 就是与"后"数组元素出列的这个元素构成的逆序对个数

            """
            for i in range(l, r + 1):
                temp[i] = nums[i]
            i = l
            j = mid + 1
            res = 0
            for k in range(l, r + 1):
                if i > mid:
                    nums[k] = temp[j]
                    j += 1
                elif j > r:
                    nums[k] = temp[i]
                    i += 1
                elif temp[i] <= temp[j]:
                    # 不统计逆序对，只做排序
                    nums[k] = temp[i]
                    i += 1
                else:
                    assert temp[i] > temp[j]
                    nums[k] = temp[j]
                    j += 1
                    # 快就快在这里，一次可以数出一个区间的个数的逆序对
                    # 例：[7,8,9][4,6,9]，4 与 7 以及 7 前面所有的数都构成逆序对
                    res += (mid - i + 1)
            return res

说明：归并两个有序数组的时候，我们要借助额外的辅助空间，为此可以全局使用一个和原始数组等长的辅助数组，否则每一次进入 merge 函数都要 new 新数组，开销很大。

上述解法的缺点是修改了原始数组，排序完成以后，逆序数就计算出来了。为此：（1）我们可以引入一个索引数组；（2）或者直接拷贝一个原始数组，这样就不用修改原始数组了。

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/