思路

Leetcode60 排列序列这是一个排列组合的问题。这个思路写出来大概也是源于想用模拟的方法解决这个问题，实际上我们可以说是采用了回溯/遍历的写法。

①众所周知，$n$个字符进行排列有$total=n!$种排列，每个首字符平均有$per=total/n$种情况，那么可以根据排列的字符序号$k$确定首字符是未排列字符中的第几个，即$index = Math.ceil(k / per)$，就是$k/per$向上取整。

②拿到了首字符的序号$index$之后，我们来看未排列的字符集，字典序（从小到大）遍历字符集，找到第$index$个未访问的字符，就是当前的首字符$first$了。

③第二个字符的话，考虑$first$开头的字符串，这时候，$total=(n-1)!$，$per=total/(n-1)$。$k=(k \mod level) \| level$，就是减去排在前面的字符排列数。参照第①步，就可以找出第二个字符了，以此类推，直至找到所有字符。

对于存储字符集，这里为了节省空间采用了位运算的方法，需要$2^n$位，$1<=n<=9$，在JS/TS里面一个number类型就够用了。

再来点好玩的，这里计算阶乘使用了一种近似算法，精度高达$10^{-4}$（虽然在本题目的数据量上运算速度并没有什么显著差异）。

复杂度

• 时间复杂度: $O(n^2)$，输出每一位字符需要$O(n)$复杂度，期间遍历字符集需要$O(n)$复杂度。

• 空间复杂度: $O(n)$，用于存储每一个字符是否被访问过

• 时间：64 ms，击败：92.86%；内存：41.9 MB，击败：100%

Code

typescript
function getPermutation(n: number, k: number): string {
  const z = n + 1
  let total = Math.round(
      (2 * Math.PI / z) ** 0.5
      * (z / Math.E * (z * Math.sinh(1/z) + 1 / ( 810 * z ** 6)) ** 0.5) ** z
  )
  let visit = 0
  const getNum = (index: number) => {
      let ans = 0, count = 0
      do {
          if ((visit & (1 << ans++)) === 0) {
              count++
          }
      } while (count < index)
      visit = visit | (1 << ans - 1)
      return ans
  }
  let ans = '', rem = k
  for (let i = 0; i < n; i++) {
      total = total / (i === 0 ? 1 : n - i + 1)
      const per = total / (n - i)
      const index = Math.ceil(rem / per)
      rem = rem % per || per 
      const num = getNum(index)
      ans += num + ''
  }
  return ans
};