leetcode_60. 第k个排列
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123" "132" "213" "231" "312" "321" 给定 n 和 k，返回第&n...
目录
一、题目内容
给出集合 [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"
示例 2:
输入: n = 4, k = 9
输出: "2314"
二、解题思路
1.从高位到低位依次进行确定。
2.每次循环得到低一位的阶乘，然后用k除以这个低一位的阶乘得到高位，然后k-高位*低一位的阶乘得到低一位的k，如此循环。
3.每找到一个高位则将其加入到res中，同时candidate里要删除掉这个被选的高位。
三、代码
-
import math
-
-
-
class Solution:
-
def getPermutation(self, n: int, k: int) -> str:
-
ans = ''
-
-
def jiecheng(n):
-
if n <= 1:
-
return 1
-
else:
-
return n * jiecheng(n - 1)
-
-
candidate = list(range(1, n + 1))
-
res = []
-
-
while candidate:
-
low_jiecheng = jiecheng(len(candidate) - 1)
-
high_index = math.ceil(k / low_jiecheng) - 1
-
high_num = candidate[high_index]
-
res.append(high_num)
-
candidate.remove(high_num)
-
k = k - high_index * low_jiecheng
-
ans = ''
-
for i in range(len(res)):
-
ans += str(res[i])
-
-
return ans
-
-
-
if __name__ == '__main__':
-
n = 3
-
k = 3
-
s = Solution()
-
ans = s.getPermutation(n, k)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。
原文链接：nickhuang1996.blog.csdn.net/article/details/108416074
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）