Leetcode 60

class Solution {
    int fact(int n){
        int ret = 1;
        for(int i = 2; i <= n; i++){
            ret *= i;
        }
        return ret;
    }
public:
    string getPermutation(int n, int k) {
        stringstream ss;
        vector<int> digits;
        for(int i = 1; i <= n; i++) digits.emplace_back(i);
        k--;
        while(n > 0){
            int slice = fact(n) / n;
            ss << digits[k / slice];
            digits.erase(digits.begin() + (k / slice));
            k = k % slice;
            n--;
        }
        return ss.str();
    }
};

我们分析全排列的结果就好理解了。

比如 n = 3，我们有：

"123"
"132"

"213"
"231"

"312"
"321"

然后你观察开头的数字，1 2 3 每一个数字都占了两种排列，最后总共六种排列。

这个规律告诉我们，对于给定的 n，开头数字为 i 的排列就会有 n! / n = (n - 1)! 种。我们记这个数为 slice.

根据这个规律，我们可以直接算出第 k 个排列的开头数字，那就是 (k - 1) / slice

接下来就可以一步步地递推得到所有数字，只不过要把已经用过的数字从备选数字中剔除。

详情就可以阅读代码了。