[LeetCode] 60. 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 for n = 3:

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

Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

思路

以 n = 3, k = 3 为例：

1. 首先确定序列的第一位，2! = 2, 所以以某一个数字开头的序列有 2 个，t = ceil(n / 2) = 2, 所以 第 3 个序列在第二小数字开头的序列里的第 k - (t - 1) * (2!) = 1 位。

2. 所以答案就变成了 第二小的数字 + 剩余数字组成的第一小的序列。

3. 剩余数字组成的第一小的序列可以用 1 的方法去求。

代码

class Solution {
public:
    string getPermutation(int n, int k) {
        int len = n;
        int num[n+1], fac[n+1];
        for (int i = 1; i <= n; i++) num[i] = i;
        fac[0] = 1;
        for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i;
        string ans;
        for (int i = n-1; i >= 1; i--) {
            int t = ceil(1.0 * k / fac[i]);
            k = k - (t - 1) *  fac[i];
            ans += (char)(num[t] + '0');
            for (int j = t; j < len; j++) {
                num[j] = num[j+1];
            }
            len--;
        }
        ans += (char) (num[1] + '0');
        return ans;
    }
};