题目描述

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

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

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

示例

示例 1：

1 2	`输入：n = 3, k = 3 输出："213"`

示例 2：

1 2	`输入：n = 4, k = 9 输出："2314"`

示例 3：

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

提示：

1 2	`1 <= n <= 9 1 <= k <= n!`

代码

模拟 + 回溯 + 剪纸 (c++)

效率较低，对大数目运算会超时。

class Solution {
private: 
    int len;
public:
    bool bl = false;
    string getPermutation(int n, int k) {
        string tmp, res;
        for (int i = 1; i < n + 1; ++i) {
            tmp += to_string(i);
        }
        len = n;
        unordered_set<string> st;
        int count = 0;
        dfs(st, tmp, res, count, k, 0);
        return res;
    }
    void dfs(unordered_set<string>& st, string tmp, string& res, int &count, int k, int begin) {
        if (bl) return ;
        if (begin + 1 == this->len) {
            if (st.count(tmp)) return ;
            st.insert(tmp);
            ++count;
        }
        if (count == k && !bl) {
            res = tmp;
            bl = true;
            return ;
        }
        for (int i = begin; i < this->len; ++i) {
            char tp = tmp[i];
            tmp[i] = tmp[begin];
            tmp[begin] = tp;
            
            /* do something */
            dfs(st, tmp, res, count, k, begin+1);

            // tmp[begin] = tmp[i];
            // tmp[i] = tp;
        }
    }
};

数学 + 缩小问题规模

c++

class Solution {
public:
    string getPermutation(int n, int k) {

        vector<int> v1(n);
        vector<int> v2(n, 1);
        v1[0] = 1;

        for (int i = 1; i < n; ++i) {
            v1[i] = v1[i - 1] * i;
        }

        string res;
        --k;
        for (int i = 1; i < n + 1; ++i) {
            int tmp = k / v1[n - i] + 1;
            for (int j = 1; j < n + 1; ++j) {
                tmp -= v2[j - 1];
                if (!tmp) {
                    v2[j - 1] = 0;
                    res += (j + '0');
                    break;
                }
            }
            k %= v1[n - i];
        }
        return res;
    }
};

java

class Solution {
    public String getPermutation(int n, int k) {
        int[] n1 = new int[n];
        int[] n2 = new int[n];
        Arrays.fill(n2, 1);
        n1[0] = 1;
        for (int i = 1; i < n; ++i) {
            n1[i] = n1[i - 1] * i;
        }
        StringBuilder res = new StringBuilder();

        --k;
        for (int i = 1; i < n + 1; ++i) {
            int tmp = k / n1[n - i] + 1;
            for (int j = 1; j < n + 1; ++j) {
                tmp -= n2[j - 1];
                if (tmp == 0) {
                    res.append(j);
                    n2[j - 1] = 0;
                    break;
                }
            }
            k %= n1[n - i];
        }
        return res.toString();
    }
}

python3

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        n1 = [1]
        n2 = [1] * n
        for i in range(1, n):
            n1.append(n1[-1] * i)
        k -= 1
        res = list()
        for i in range(1, n + 1):
            tmp = k // n1[n - i] + 1
            for j in range(1, n + 1):
                tmp -= n2[j - 1]
                if tmp == 0:
                    res.append(str(j))
                    n2[j - 1] = 0
                    break 
            k %= n1[n - i]
        return "".join(res)