Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

解题思路:
对于n个数，可以构成的排列有n!中，而对于第k个排列，我们可以这样理解

最高位为1:则所有的数的范围在 1 ~ (n - 1)!                0
       2：则所有的数的范围: (n- 1)! + 1 + 2(n - 1)!     1


       每个范围的长度均为(n - 1)!,我们可以确定k在哪个区间中

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<long> per(n+1);
        per[0] = 1;
        vector<int> nums;
        string res;

        long base = 1;
        for(int i = 1; i <= n; i++){
            base *= i;
            per[i] = base;
        }

        for(int i = 1; i <=n; i++ )
            nums.push_back(i);
        k--;

        for(int i = 1; i <= n; i++){
            int index = k / per[n - i];
            res += nums[index] + '0';
            nums.erase(nums.begin() + index);
            k -= index * per[n - i];
        }

        return res;
    }
};