题目描述

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

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

• “123”
• “132”
• “213”
• “231”
• “312”
• “321”

给定 n 和 k，返回第 k 个排列。

说明：

• 给定 n 的范围是 [1, 9]。
• 给定 k 的范围是[1, n!]。

样例

输入: n = 3, k = 3
输出: "213"

输入: n = 4, k = 9
输出: "2314"

算法分析

• 当要确定第i位是什么数时，后面的n - i个位置有(n - i)!种放法，可以知道每次满(n - i)!时，第i位数可以进1，因此第i位数的值是 当前没有枚举过的第 $\lceil \frac{k}{(n - i)!} \rceil$ 个数，具体操作看下面的例子

n = 5,k = 40

第一位数：
    k = 40
    idx = 40 / 4! 上取整 = 2
    因此第1位数放的是当前没有枚举过的第2个元素，即第1位数是 2
    k -= (idx - 1) * 4! = 16

第二位数：
    k = 16
    idx = 16 / 3! 上取整 = 3
    因此第2位数放的是当前没有枚举过的第3个元素，即第2位数是 4  (2已经被枚举过)
    k -= (idx - 1) * 3! = 4

第三位数：
    k = 4
    idx = 4 / 2! 上取整 = 2
    因此第3位数放的是当前没有枚举过的第2个元素，即第3位数是 3  (2已经被枚举过)
    k -= (idx - 1) * 2! = 2

第四位数
    k = 2
    idx = 2 / 1! 上取整 = 2
    因此第4位数放的是当前没有枚举过的第2个元素，即第4位数是 5  (2,3,4已经被枚举过)
    k -= (idx - 1) * 1! = 1

第五位数
    k = 1
    idx = 1 / 0! 上取整 = 1
    因此第5位数放的是当前没有枚举过的第1个元素，即第4位数是 1  
    k -= (idx - 1) * 0! = 1

因此答案是："24351"

时间复杂度 $O(n^2)$

Java 代码

class Solution {

    public String getPermutation(int n, int k) {
        boolean[] st = new boolean[10];
        int[] f = new int[10];
        f[0] = 1;
        for(int i = 1;i <= n;i ++) f[i] = f[i - 1] * i;
        String ans = "";
        for(int i = n - 1;i >= 0;i --)
        {
            int idx = (k + f[i] - 1) / f[i];//上取整
            //找到第idx个没有遍历过的数
            int count = 0;
            for(int j = 1;j <= n;j ++)
            {
                if(st[j]) continue;
                count ++;
                if(count == idx)
                {
                    st[j] = true;
                    ans += j;
                    break;
                } 
            }
            k -= (idx - 1) * f[i];
        } 
        return ans;
    }
}