60. Permutation Sequence 第 K 个字典序排列

string getPermutation(int n, int k) {
    string a(n, '0');
    for(int i=1;i<=n;++i) a[i-1]+=i;
    if (n == 1 || k == 1) return a;
    for(int i=0;i<k-1;i++) next_permutation(a.begin(), a.end());
    return a;
}

string getPermutation(int n, int k) {
    string a(n, '0');
    int i;
    for(i=1;i<=n;++i) a[i-1]+=i;
    if (n == 1 || k == 1) return a;

	// 阶乘的记忆数组
    vector<int> v(n, 1);
    for(i=n-3;i>=0;--i) v[i] = v[i+1]*(n-1-i);

    k--;
    string res(n, '0');
    for(i=0;i<n;++i) {
        int select = k/v[i];
        k %= v[i];
        res[i] = a[select];
		// 选了一位字符后要从候选字符中去除
        a.erase(select, 1);
    }
    return res;
}