题目描述

题目链接：60. Permutation Sequence

Given n and k, return the kth 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:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

例子

例子 1

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

例子 2

Input: n = 4, k = 9 Output: "2314"

例子 3

Input: n = 3, k = 1 Output: "123"

Constraints

• 1 <= n <= 9
• 1 <= k <= n!

解题思路

在题目中给出的例子中可以发现，对于 n = 3 的所有情况，可以按照首元素 1 和 2 和 3 均等的分为 3 组，每一组中有 (n - 1)! 个。以此我们可以发现一个规律，对于 n 个数字的排列情况来说，它的所有排列可以分为 n 组，每组中有 (n - 1)! 个子排列。我们要求第 k 个的话，第一步可以首先用 k / (n - 1)! 就知道我们要求的排列落在哪一个组中，在对于该组中我们递归的用 k = k % (n - 1)!， n = n - 1 进行重复计算即可，终止情况是 n = 1 此时只有一种排列即该数字本身。具体操作过程中，由于每次循环我们都会用掉一个元素，所以需要在该序列中，把那个数字去掉。

代码如下：

#include <string>
#include <vector>

class Solution {
public:
    std::string getPermutation(int n, int k) {
        std::vector<int> nums;
        std::vector<int> factorial(10, 1);
        for (int i = 1; i <= 9; i++) {
            nums.push_back(i);
            factorial[i] = factorial[i - 1] * i;
        }

        std::string perm = "";
        k--;
        while (n > 0) {
            int select = k / factorial[n - 1];
            k %= factorial[n - 1];

            perm += '0' + nums[select];
            for (int i = select; i < nums.size() - 1; ++i) {
                nums[i] = nums[i + 1];
            }

            n--;
        }

        return perm;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 60.PermutationSequence.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions