阶乘问题

Paste_Image.png

class Solution(object):
    """
    :type n: int
    :type k: int
    :rtype: str
    """
    def getPermutation(self, n, k):
        jc = [1]#存放阶乘的数组
        num = [] #存放序列1,2,3,4
        for i in range(2,n):
            jc.append(jc[-1]*i)
        for i in range(n):
            num.append(i+1)
        result = "" #返回的字符串

        #循环判断第i个值的位置
        for i in range(n-1):
            if k == 0 or k == 1:
                break
            #当前所在区间
            s = int(k/jc[n-i-2])
            if k%jc[n-i-2] > 0:
                s+=1
            #m放在第一个位置的下标
            m = s - 1
            #新k，
            k -= jc[n-i-2] * (s-1)
            #调整位置
            temp = num[m+i]
            while m > 0:
                num[m+i] = num[m+i-1]
                m -= 1
            num[i] = temp
        result = ""
        for i in range(len(num)):
            result += str(num[i])
        return result
s = Solution()
s.getPermutation(3,6)