60. 排列序列

难度 hard
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出："213"
示例 2：

输入：n = 4, k = 9
输出："2314"
示例 3：

输入：n = 3, k = 1
输出："123"

提示：

1 <= n <= 9
1 <= k <= n!

解题思路：例如： n = 6, k = 373,
初始化数组 num = [1, 2, 3, 4, 5, 6];
首先应该明白，以1开头的全排列有5!个，以2开头的全排列有5!个，以3开头…… 共5!?6=6! 个；

故 k = 373 时，全排列的第一个数字应该是nums[ k/5!]=4 ;
数组删除4, 此时 nums = [1, 2, 3, 5, 6]; k = k % 5! = 12;
接下来就是在nums 中找第12个全排列，重复 1，2 步即可 。

代码 t37 s28 java

class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder(n);
        ArrayList<Integer> factorial = new ArrayList<>();
        ArrayList<Integer> num = new ArrayList<>();
        factorial.add(1);
        for(int i=1; i<=n; i++){
            factorial.add(factorial.get(i-1)*i);
            num.add(i);
        }
        k--;
        for(int i=1; i<=n; i++){
            int order = k / factorial.get(n-i);
            // System.out.println(order);
            sb.append(num.get(order));
            for(int j=order; j<n-i; j++){
                num.set(j, num.get(j+1));
            }
            k = k % factorial.get(n-i);
        }
        
        return sb.toString();
    }
}

注意中间有一个k--的操作，还是基1的顺序和基0的索引导致的问题，比如n=3，k=6，此时factorial=[1,1,2,3]，num=[1,2,3]，如果k不减1，第一轮循环会出现k/2=3,而num并不存在索引为3的数，所以就会出错，因此k--，本质上就是一个变基的过程，相当于floor，以便找到合适的num索引。

参考资料：

https://leetcode-cn.com/problems/permutation-sequence/solution/cyu-yan-chao-jian-dan-de-chu-fa-ding-wei-by-dingji/

60. 排列序列

原文：https://www.cnblogs.com/zhengxch/p/14673006.html