Permutation Sequence

    Example

    For , all permutations are listed as follows:

    Note

    n will be between 1 and 9 inclusive.

    Challenge

    和题 Permutation Index 正好相反，这里给定第几个排列的相对排名，输出排列值。和不同进制之间的转化类似，这里的『进制』为1!, 2!..., 以n=3, k=4为例，我们从高位到低位转化，直觉应该是用 , 但以 n=3,k=5 和 n=3,k=6 代入计算后发现边界处理起来不太方便，故我们可以尝试将 k 减1进行运算，后面的基准也随之变化。第一个数可以通过(k-1)/(n-1)!进行计算，那么第二个数呢？联想不同进制数之间的转化，我们可以通过求模运算求得下一个数的, 那么下一个数可通过(k2 - 1)/(n-2)!求得，这里不理解的可以通过进制转换类比进行理解。和减掉相应的阶乘值是等价的。

    Python

    Java

    1. 建阶乘数组
    2. 生成排列数字数组
    3. 从高位到低位计算排列数值

    复杂度分析

    几个 for 循环，时间复杂度为 O(n), 用了与 n 等长的一些数组，空间复杂度为 O(n).