这篇文章主要介绍LeetCode如何找出数组中的逆序对，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
成都创新互联公司专注于高安网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供高安营销型网站建设，高安网站制作、高安网页设计、高安网站官网定制、微信小程序开发服务，打造高安网络公司原创品牌,更为您提供高安网站排名全网营销落地服务。
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
0 <= 数组长度 <= 50000
题目样例
示例
题目思考
解决方案
思路
- 一个比较容易想到的思路是双重循环, 暴力求逆序对, 但这样时间复杂度是 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如何找出数组中的逆序对”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联行业资讯频道！
分享题目：LeetCode如何找出数组中的逆序对
文章链接：
http://cdkjz.cn/article/ieppds.html
