60. Permutation Sequence-排列序列

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

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

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "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!

1.DFS
Python:

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        f = [1 for i in range(n+1)]
        for i in range(2, n+1):
            f[i] = f[i-1]*i
        flag = [False for i in range(n)]
        result = []

        def dfs(n, k, index, temp):
            if n == index:
                return 
            c = f[n-index-1]
            for i in range(n):
                if flag[i]:
                    continue
                if c < k:
                    k -= c 
                    continue
                temp.append(str(i+1))
                flag[i] = True
                dfs(n, k, index+1, temp)
                return 

        dfs(n, k, 0, result)
        return ''.join(result)

Java:

class Solution {
    public String getPermutation(int n, int k) {
        int[] f = new int[n+1];
        boolean[] flag = new boolean[n];
        Arrays.fill(f, 1);
        Arrays.fill(flag, false);
        for(int i = 2; i < f.length; i++)
        {
            f[i] = f[i-1]*i;
        }
        StringBuilder result = new StringBuilder();
        dfs(n, k, 0, result, flag, f);
        return result.toString();
    }

    public void dfs(int n, int k, int index, StringBuilder temp, boolean[] flag, int[] f)
    {
        if(n == index)
            return;
        int c = f[n-index-1];
        for(int i = 0; i < n; i++)
        {
            if(flag[i])
                continue;
            if(c < k)
            {
                k -= c;
                continue;
            }
            temp.append(i+1);
            flag[i] = true;
            dfs(n, k, index+1, temp, flag, f);
            return;
        }
    }
}