您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要介绍LeetCode如何找出数组中的逆序对,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
0 <= 数组长度 <= 50000
N+(N/2)*2+(N/4)*4+...+1*N = NlogN
, 因为一共 logN
个乘积)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如何找出数组中的逆序对”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。