当前位置:
首页 > temp > 简明python教程 >
-
LeetCode 面试题51. 数组中的逆序对
面试题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
实现结果
以上就是使用归并排序的思想,解决《面试题51. 数组中的逆序对》问题的主要内容。
栏目列表
最新更新
nodejs爬虫
Python正则表达式完全指南
爬取豆瓣Top250图书数据
shp 地图文件批量添加字段
爬虫小试牛刀(爬取学校通知公告)
【python基础】函数-初识函数
【python基础】函数-返回值
HTTP请求:requests模块基础使用必知必会
Python初学者友好丨详解参数传递类型
如何有效管理爬虫流量?
2个场景实例讲解GaussDB(DWS)基表统计信息估
常用的 SQL Server 关键字及其含义
动手分析SQL Server中的事务中使用的锁
openGauss内核分析:SQL by pass & 经典执行
一招教你如何高效批量导入与更新数据
天天写SQL,这些神奇的特性你知道吗?
openGauss内核分析:执行计划生成
[IM002]Navicat ODBC驱动器管理器 未发现数据
初入Sql Server 之 存储过程的简单使用
SQL Server -- 解决存储过程传入参数作为s
关于JS定时器的整理
JS中使用Promise.all控制所有的异步请求都完
js中字符串的方法
import-local执行流程与node模块路径解析流程
检测数据类型的四种方法
js中数组的方法,32种方法
前端操作方法
数据类型
window.localStorage.setItem 和 localStorage.setIte
如何完美解决前端数字计算精度丢失与数