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 for n= 3:
"123""132""213""231""312""321"Given n and k, return the kth permutation sequence.
Note:
Given n will be between 1 and 9 inclusive.Given k will be between 1 and n! inclusive.Example 1:
Input: n = 3, k = 3 Output: "213"Example 2:
Input: n = 4, k = 9 Output: "2314"分析
计算第k个字符串时，我们需要知道当前字符串长度为n时，其组成的可能字符串的数。
n=1, 1
n=2, 2
n=3, 6
加入给定n=4, k=9， 使用nums存放[1, n]的数组，那么第一个数字是nums[(k-1)/6] = 2。即以1为首的组合有6种，那么k=9时，开头一定是2。接下来继续找，此时应该寻找以2开头的第3个字符串，那么可以确认此时应该是找到第（3-1）/2个数字，即3。几次类推的找下去即可得到最终的结果。
Code
class Solution { public: string getPermutation(int n, int k) { vector<int> nums(n, 1); vector<int> dp(n, 1); for (int i = 1; i < n; i ++) { dp[i] = dp[i-1] * i; nums[i] = i+1; } vector<int> res; k = k-1; for (int i = n-1; i >= 0; i --) { res.push_back(nums[k/dp[i]]); nums.erase(nums.begin()+ k/dp[i]); k = k % dp[i]; } string s; for (int i = 0; i < res.size(); i ++) { s += to_string(res[i]); } return s; } };
运行效率
Runtime: 4 ms, faster than 94.95% of C++ online submissions for Permutation Sequence.
Memory Usage: 8.6 MB, less than 57.87% of C++ online submissions forPermutation Sequence.
