leetcode刷题-60第k个队列
2024-10-09 10:30:25
题目
给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k,返回第 k 个排列。
说明:
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
思路
最开始的想法是列出全排列后,选出第k个,但是时间效率太低无法通过。看了官网解答也没看懂,后来发现可以用找规律的方式来确定。
以示例为例,所有排列可以理解为1+(2,3)的排列,2+(1,3)的排列,3+(1,2)的排列。当k =3时,其一定存在于k//(n-1)!=2//2!=1中(k需要-1,因为索引起始为0),因此其在数组[1,2,3]的索引为1,其值为2,其余数为0,在(2,3)的排列排列中,其存在与0//1! = 0中(k =2)其值为1,最后在(3)的排列中,由此得到"213".
实现
class Solution:
def getPermutation(self, n: int, k: int) -> str:
nums = [str(i) for i in range(1,n+1)]
result = ''
k = k-1
def factorial(n):
sum=1
for i in range(1,n+1):
sum*=i
return sum while n > 0:
n -= 1
num, k = divmod(k, factorial(n))
result += nums.pop(num)
return result
最新文章
- MVC2,MVC3,MVC4和MVC5的不同
- spring定时器
- fatal: Could not read from remote repository.的解决办法
- easyUI之message
- windows 10 笔记本关机不断电解决
- 写一个Windows上的守护进程(5)文件系统重定向
- IOS app启动过程
- centos6.8安装superctl 后台管理工具
- 通过实例来理解ajax
- pulltorefresh 设置刷新文字提示颜色
- 内置函数 -- bytes -- 字节码与字符串相互转换
- MySQL 复制 - 性能与扩展性的基石 4:主备切换
- 下载 youtube 油管的视频
- [转]从minio中读取文件流进行下载文件
- Centos安装elasticsearch教程
- eclipse中没有tomcat小猫
- DbgPrint/KdPrint输出格式控制
- Vue 自定义header
- jquery获取元素在文档中的位置信息以及滚动条位置(转)
- Neutron命令测试3