返回第k个排列

[编程题]返回第k个排列

热度指数：10822 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

集合[1,2,3,…,n]一共有n!种不同的排列

按字典序列出所有的排列并且给这些排列标上序号

我们就会得到以下的序列（以n=3为例）

"123"
"132"
"213"
"231"
"312"
"321"

现在给出n和k，请返回第k个排列

注意：n在1到9之间

示例1

输入

3,1

输出

"123"

算法知识视频讲解

Python

黄沙遮天

方法1（暴力破解）：先进行全排列，然后返回对应的第k-1元素就行了

#
# 
# @param n int整型 
# @param k int整型 
# @return string字符串
#
class Solution:
    def perm(self,s,list1,totallist):
        if len(list1)==0:
            temstr=""
            for i in s:
                temstr+=i
            totallist.append(temstr)
            return
        for i in range(len(list1)):
            self.perm(s+list1[i],list1[:i]+list1[i+1:],totallist)
    def getPermutation(self , n , k ):
        # write code here
        if n==0:
            return ""
        list1=[str(i) for i in range(1,n+1)]
        totallist=[]
        self.perm('',list1,totallist)
        return totallist[k-1]

编辑于 2020-09-21 17:35:27 回复(0)