LeetCode如何找出数组中的逆序对

发布时间:2021-12-15 13:58:25 作者:小新
来源:亿速云 阅读:143

这篇文章主要介绍LeetCode如何找出数组中的逆序对,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

0 <= 数组长度 <= 50000

           

题目样例

           

示例

  • 输入: [7,5,6,4]
  • 输出: 5
           

题目思考

  1. 如何批量得到逆序对?
           

解决方案

           
思路
  • 一个比较容易想到的思路是双重循环, 暴力求逆序对, 但这样时间复杂度是 O(N^2), 根据数据规模肯定超时, 如何进行优化呢?
  • 如果我们能将问题进行分解, 先求出数组左右两部分的逆序对数目, 最后再一次遍历将分属两部分的逆序对(也即第一个数在左半部分, 第二个数在右半部分)也求出来并累加在一起, 这样就能优化时间复杂度到 O(NlogN), 这就是分治法的思想
  • 此时关键在于如何一次遍历就求得分属两部分的逆序对呢? 如果左右两部分是有序的就很好办了, 可以利用归并排序的思路, 双指针遍历, 哪边小就把哪边加入结果数组中. 如果是右侧小的话就意味着左侧剩余的数字都和当前右侧数字构成逆序对, 将对应的数目加入结果中即可.
  • 而左右部分有序正好也是归并排序的结果, 所以整个思路就是在归并排序的基础上加上逆序对的统计
  • 下面代码对必要的步骤有详细的解释, 方便大家理解
           
复杂度
  • 时间复杂度 O(NlogN): 使用了归并排序, 时间复杂度是( N+(N/2)*2+(N/4)*4+...+1*N = NlogN, 因为一共 logN 个乘积)
  • 空间复杂度 O(N): 归并排序需要用到临时数组, 长度为 N
           
代码
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.res = 0

        def mergesort(s, e):
            if s >= e:
                return
            m = (s + e) >> 1
            # 先排序并统计左右部分
            mergesort(s, m)
            mergesort(m + 1, e)
            # 使用临时数组存储排序好的左右部分
            # 注意这里选择逆序存储, 是因为可以利用O(1)的pop操作得到最小的元素
            # 当然这里也可以使用双端队列, 这样就无需逆序了
            left = nums[s:m + 1][::-1]
            right = nums[m + 1:e + 1][::-1]
            for i in range(s, e + 1):
                if not right or left and left[-1] <= right[-1]:
                    # 当前左侧数字更小或者右侧数字已经用完, 此时不构成逆序对
                    nums[i] = left.pop()
                else:
                    # 当前右侧数字更小, 和剩余的左侧部分都构成逆序对
                    self.res += len(left)
                    nums[i] = right.pop()

        mergesort(0, len(nums) - 1)
        return self.res

以上是“LeetCode如何找出数组中的逆序对”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!

推荐阅读:
  1. 剑指offer:数组中的逆序对
  2. LeetCode如何找出链表的中间节点

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:Qt技巧怎么使用

下一篇:Qt如何实现设备监控

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》