Skip to content

60. Permutation Sequence

https://leetcode.com/problems/permutation-sequence/

js
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function(n, k) {
  var fac = [1]
  for (let i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i
  }

  var str = []
  for (let i = 1; i <= n; i++) {
    str.push('' + i)
  }

  var result = []
  for (let i = 0; i < n; i++) {
    let index = (k - 1) / fac[n - i - 1] >> 0
    result.push(str[index])
    str.splice(index, 1)
    k = (k - 1) % fac[n - i - 1] + 1
  }

  return result.join('')
}
py
class Solution(object):

    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        fac = [1]
        for i in range(1, n + 1):
            fac.append(fac[-1] * i)

        chs = [str(i) for i in range(1, n + 1)]
        result = []
        for i in range(n):
            index = (k - 1) // fac[n - i - 1]
            result.append(chs.pop(index))
            k = (k - 1) % fac[n - i - 1] + 1

        return ''.join(result)