彩虹岛无限回廊,电脑机箱漏电,慈溪职高黄瓜门
题目来源:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 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
以上就是使用归并排序的思想,解决《面试题51. 数组中的逆序对》问题的主要内容。
欢迎关注微信公众号《书所集录》
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
Python 实现将numpy中的nan和inf,nan替换成对应的均值
python爬虫把url链接编码成gbk2312格式过程解析
网友评论