1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— LOCF.51. 数组中的逆序对

flypython • • leetcode题解

LOCF.51. 数组中的逆序对

链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
难度：中等

题目

点击原文链接跳转查看题目

思路

这题如果暴力的话，时间复杂度为O(N*N)，会超时，具体代码请看超时方案。

那怎么才能降低复杂度呢？在这里我们可以想到归并排序，为什么呢？

那是因为此题的逆序对其实可以在归并排序中的最后阶段———合并有序数组中得到。

方案代码

超时方案：

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        count = 0
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                if nums[i] > nums[j]:
                    count += 1
        
        return count

解决方案：


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(l=0, r=len(nums)):#左闭右开区间
            if r - l > 1:
                mid = (l + r)//2
                mergeSort(l, mid)
                mergeSort(mid, r)
                i, j, tmp = l, mid, []
                while i < mid and j < r:
                    if nums[i] <= nums[j]:
                        tmp.append(nums[i])
                        i += 1
                    else:
                        tmp.append(nums[j])
                        j += 1
                        self.cnt += mid - i
                tmp.extend(nums[i:mid] if i<mid else nums[j:r])
                nums[l:r] = tmp

        self.cnt = 0
        mergeSort()
        return self.cnt

原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/350.html

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 23/04/2020 11:03
下一篇 » 25/04/2020 11:05

相关推荐