[leetcode]Permutation Sequence

思想很简单,细节有点小麻烦的题.

直接next_permutation我觉得应该可以的,不过好慢,可能TLE吧

然后就是用数学方法了..

一位一位的确认

除去第一位,后面有(n-1)!种排列.

那么第一位就是k / (n-1)! (这结果只是下标啦,k从0开始,所以我们要预先k--

这个是下标,从还存在的从小到达的数组里面的下标,表示选哪个

然后 k %= (n-1)! base/=n-1

如此迭代下去

class Solution {
public:
    int fac(int n) {
        int res = 1;
        for(int i = 2 ; i <= n ; ++i) 
          res *= i;
        return res;
    }
    string getPermutation(int n, int k) {
        string digit(n,'0');
        string result = "";
        for(int i = 0 ; i < n ; ++i)
          digit[i] += i + 1;
        k--;
        int base = fac(n-1);
        for(int i = n-1 ; i > 0 ; k%=base , base/=i , --i) {
            int idx = k/base;
            char ch = digit[idx];
            result.push_back(ch);
            digit.erase(digit.begin() + idx);
        }
        result.push_back(digit[0]);
        return result;
    }
};