LeetCode #60 排列序列

给出集合 [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!

/**
* It's quite difficult to explain how this piece of code works...
*/
int kthdigit(int *digits, bool *flags, int n, int k) {
    for (int i = 1; i <= n; i++) {
        if (!flags[i]) k -= 1;
        if (k == 0) return digits[i];
    }
    return 0;
}
char * getPermutation(int n, int k){
    char *s = (char*)malloc((n + 1) * sizeof(*s));
    s[n] = '\0';
    
    int np[n + 1], lo = 1;
    np[0] = 1;
    do {
        np[lo] = np[lo - 1] * lo;
    } while (np[lo++] < k);
    lo -= 1;
    if (np[lo] == k) {
        for (int i = 0; i < n - lo; i++) { s[i] = (char)(i + 1) + '0'; }
        for (int i = n - lo; i < n; i++) { s[i] = (char)(n - (i - (n - lo))) + '0'; }
    } else {
        int digits[n + 1];
        bool flags[n + 1];
        for (int i = 1; i <= n; i++) {
            digits[i] = i;
            flags[i] = false;
        }

        lo -= 1;
        for (int i = 0; i < n - lo - 1; i++) {
            s[i] = (char)(i + 1) + '0';
            flags[i + 1] = true;
        }

        

        for (int i = n - lo - 1; i < n; i++) {
            int kth = n - i;
            if (k > 0) {
                kth = (int)ceil((double)k / (double)np[lo]);
                k %= np[lo--];
            }
            
            int digit = kthdigit(digits, flags, n, kth);
            s[i] = (char)digit + '0';
            flags[digit] = true;
        }
    }
    

    return s;
}