1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3296.html

« [剑指 Offer 第 2 版第 49 题] “丑数”做题记录
[剑指 Offer 第 2 版第 52 题] “两个链表的第一个公共结点”做题记录»

相关推荐

QR code