LeetCode 面试题51. 数组中的逆序对(leetcode积分有什么用)

网友投稿 1570 2022-09-21

LeetCode 面试题51. 数组中的逆序对(leetcode积分有什么用)

LeetCode 面试题51. 数组中的逆序对(leetcode积分有什么用)

面试题51. 数组中的逆序对

题目来源:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

题目

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

示例 1:

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

输出: 5

解题思路

思路:归并排序

归并排序使用了分治的思想,这个过程需要使用递归来实现。在分治算法递归实现中,每层递归会涉及三个步骤:

分解:将原问题分解为一系列子问题;

解决:递归求解各个子问题,若子问题足够小,直接求解;

合并:将子问题的结果合并为原问题。

在本题当中,

分解:假设区间为 [left, right],令 mid = [(left + right) / 2],将 [left, right] 分成 [left, mid] 和 [mid + 1, right];

解决:使用递归排序两个子序列;

合并:将已经排好的子序列 [left, mid] 和 [mid + 1, right] 合并

题目中要求返回数组构成逆序对的总数。逆序对:即是前面的一个数字大于后面的数字,那么这两个数字可以构成一个逆序对。

具体思想参考代码

代码实现

class Solution:

def reversePairs(self, nums: List[int]) -> int:

n = len(nums)

if n < 2:

return 0

# 辅助数组,用于归并

temp = [0] * n

return self.count_invs(nums, 0, n - 1, temp)

def count_invs(self, nums, left, right, temp):

if left == right:

return 0

mid = (left + right) // 2

left_pairs = self.count_invs(nums, left, mid, temp)

right_pairs = self.count_invs(nums, mid+1, right, temp)

# 这里表示已经排序好,并且已经计算左右两部分未排序前的逆序对

invs_pairs = left_pairs + right_pairs

if nums[mid] < nums[mid + 1]:

# 这个时候表示都是顺序排序,不用计算两个区间交叉的逆序对,直接返回

return invs_pairs

# 这里计算区间交叉的逆序对

invs_cross_pairs = self.merge_count(nums, left, mid, right, temp)

return invs_pairs + invs_cross_pairs

def merge_count(self, nums, left, mid, right, temp):

# 现在两个区间都是有序的

# 合并计算此时区间交叉的逆序对个数

# 复制原数组到辅助数组

for i in range(left, right + 1):

temp[i] = nums[i]

p = left

q = mid + 1

ans = 0

for i in range(left, right + 1):

# 这里归并剩余的部分

if p > mid:

nums[i] = temp[q]

q += 1

elif q > right:

nums[i] = temp[p]

p += 1

elif temp[p] <= temp[q]:

# 这个时候,前面部分区间的元素出列

# 因为 p 对应的元素,比 q 对应的元素小

# 那么 p 对应的元素一定比 q 对应元素后面的元素都小

# 所以这个时候不统计逆序对,p 往前移动

nums[i] = temp[p]

p += 1

else:

# 这种属于相反的情况

# p 对应的元素比 q 对应的元素大,

# 那么 p 对应的元素后面的元素一定更大

# 所以,元素出列同时统计逆序对

# 这个时候,数组位置 p 到该区间末尾有多少个元素就有多少个逆序对,即是 mid - p + 1

nums[i] = temp[q]

q += 1

ans += (mid - p + 1)

return ans

实现结果

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Vmware Tools 配合SHell脚本实现自动正常关闭ESXI6.0过程
下一篇:如何查询HP-UX主机防火墙状态
相关文章

 发表评论

暂时没有评论,来抢沙发吧~