60. Permutation Sequence

超时了。。。
回溯法

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        res = []
        temp = ''
        visit = [0 for i in range(n)]
        self.huisu(visit, [0], n, k, res, temp)
        return res[0]
    def huisu(self, visit, count, n, k, res, temp):
        if count[0] >= k:
            return
        if len(temp) == n:
            count[0] += 1
            if count[0] == k:
                res.append(temp)
            return
        for i in range(1, n+1):
            if visit[i-1] == 0:
                visit[i-1] = 1
                self.huisu(visit, count, n, k, res, temp + str(i))
                visit[i-1] = 0

一种没超时的办法久久没法提交？？

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        ans=''
        nums=[]
        s=1
        for i in range(n):
            nums.append(i+1)
            s*=(i+1)
        k-=1
        while nums:
            s=s/n
            j,k=divmod(k,s)             
            ans+=str(nums.pop(j))
            n-=1            
        return ans