leetcode 60:第k个排列

直接使用全排列之后再进行提取，会超出时间限制。

本题限定了1-9可以使用简单的方式

比如 n=5;k=50;

数组为1,2,3,4,5

首先是(n-1)!=24  第一个元素应该为50/24+1 , 也就是3，代表的是没使用数组的第3个元素，也即为3,k=50%24=2

第二个元素（n-2)!=6 元素应该为2/6+1 ,也就是1 代表的是没使用的数组的第1个元素，也即1 ,k=2%6=2

第三个 元素（n-3)!=2   2/2=1 代表的是没使用的元素的第1个元素  应该数组中1已经使用  第一个没使用的即为2 ，

因为2%2==0，所以后面两个元素是降序的没使用的元素  也就是5 4

所以字符串为31254

int getN(int n){
    if(n<=1)
        return 1;
    else
        return n*getN(n-1);
}

std::string getPermutation(int n, int k) {
    std::vector<int> a;
    std::vector<int> b;
    for(int i=0;i<n;i++){
        a.push_back(i+1);
        b.push_back(0);
    }
    std::string str="";
    while(n!=0){
        int c=getN(n-1);
        if(k%c==0){
            k=k/c;
            int d=0;
            for(int i=0;i<a.size();i++){
                if(b[i]==0)
                    d++;
                if(d==k){
                    b[i]=1;
                    d=i;
                    break;
                }
            }
            char re[10];
            sprintf(re,"%d",a[d]);
            str+=re;
            for(int j=a.size()-1;j>=0;j--){
                if(b[j]!=1){
                    sprintf(re,"%d",a[j]);
                    str+=re;
                }
            }
            break;
        }else
        {
            int f=k/c+1;
            k=k%c;

            int d=0;
            for(int i=0;i<a.size();i++){
                if(b[i]==0)
                    d++;
                if(d==f){
                    b[i]=1;
                    d=i;
                    break;
                }
            }
            char re[10];
            sprintf(re,"%d",a[d]);
            str+=re;
            n--;
        }
    }
    return str;
}