C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return string字符串
     */
    int nn(int n)
    {
        if(n==0)
        {
            return 1;
        }else{
            return n*nn(n-1);
        }
    }
    string kth(string str,int k)
    {
        int n=str.size();
        if(n==1)
        {
            return str;
        }
        int k1=k/nn(n-1);
        int k2=k%nn(n-1);
        char c=str[k1];
        str.erase(k1, 1);
        return c+kth(str,k2);
    }
    string KthPermutation(int n, int k) {
        // write code here
        string str="";
        for(int i=1;i<=n;i++)
        {
            str+='0'+i;
        }
        return kth(str,k-1);
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2022-07-19

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return string字符串
     */
    int nn(int n){
        if(n == 0){
            return 1;
        }else{
            return n * nn(n - 1);
        }
    }
    
    string kth(string str, int k){
        int n = str.size();
        if(n == 1){
            return str;
        }
        int k1 = k / nn(n - 1);
        int k2 = k % nn(n - 1);
        char c = str[k1];
        str.erase(k1, 1);
        return c+kth(str, k2);
    }
    
    string KthPermutation(int n, int k) {
        string str = "";
        for(int i = 1; i <= n; i ++){
            str += '0'+i;
        }
        return kth(str, k-1);
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 408KB, 提交时间: 2022-07-10

class Solution {
public:
    string KthPermutation(int n, int k) {
        vector<int> a = toArray(n);
        while (--k > 0) {
            nextPermutation(a);
        }
        
        return to_string(toInt(a));
    }
    
private:
    vector<int> toArray(int n) {
        vector<int> v(n);
        for (int i=1; i<=n; ++i) {
            v[i-1] = i;
        }
        return v;
    }  
    int toInt(vector<int>& a) {
        int v = 0;
        for (int i=0; i<a.size(); ++i) {
            v = v * 10 + a[i];
        }
        return v;
    }    
    bool nextPermutation(vector<int>& a) {
        int f = -1, h = a.size();
        
        for (int i=h-2; i>=0; --i) {
            if (a[i] < a[i+1]) {
                f = i;
                break;
            }
        }        
        if (f == -1) {
            reverse(a.begin(), a.end());
            return false;
        }       
        for (int i=h-1; i>=f; --i) {
            if (a[i] > a[f]) {
                swap(a[i], a[f]);
                break;
            }
        }        
        reverse(a.begin() + f + 1, a.end());       
        return true;
    }
};

C 解法, 执行用时: 4ms, 内存消耗: 408KB, 提交时间: 2022-06-24

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param k int整型 
 * @return string字符串
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
char* KthPermutation(int n, int k ) {
    char *result = (char *)malloc(sizeof(char) * (n + 1));
    result[n] = '\0';
    
    int nums[n];
    memset(nums, 0, sizeof(nums));
    
    int cIndex = 0, cMod = 1, cValue = k, mod, count;
    for (int i = 1; i < n; i++) {
        cMod *= i;
    }
    
    while(cIndex < n) {
        mod = (cValue - 1) / cMod;
        cValue = cValue - mod * cMod;
        if (cIndex < n - 1) {
            cMod = cMod / (n-1-cIndex);
        }
        
        count = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                count++;
                if (count == (mod + 1)) {
                    nums[i] = 1;
                    result[cIndex++] = i + 1 + '0';
                    break;
                }
            }
        }
    }
    
    return result;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 412KB, 提交时间: 2022-04-21

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return string字符串
     */
    string KthPermutation(int n, int k) {
        // write code here
        vector<int> nums = toArray(n);
        while (--k > 0) {
            nextPermutation(nums);
        }
        
        return to_string(toInt(nums));
    }
    
private:
    vector<int> toArray(int n) {
        vector<int> ans(n);
        for (int i=1; i<=n; ++i) {
            ans[i-1] = i;
        }
        return ans;
    }
    
    int toInt(vector<int>& nums) {
        int ans = 0;
        for (int i=0; i<nums.size(); ++i) {
            ans = ans * 10 + nums[i];
        }
        return ans;
    }
    
    bool nextPermutation(vector<int>& nums) {
        int index = -1, n = nums.size();
        
        for (int i=n-2; i>=0; --i) {
            if (nums[i] < nums[i+1]) {
                index = i;
                break;
            }
        }
        
        if (index == -1) {
            reverse(nums.begin(), nums.end());
            return false;
        }
        
        for (int i=n-1; i>=index; --i) {
            if (nums[i] > nums[index]) {
                swap(nums[i], nums[index]);
                break;
            }
        }
        
        reverse(nums.begin() + index + 1, nums.end());
        
        return true;
    }
};