60.permutation-sequence

Statement

简体中文English

Metadata

• Link: 排列序列
• Difficulty: Hard
• Tag: 递归 数学

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

给定 n 和 k，返回第 k 个排列。

 

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

 

提示：

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

Metadata

• Link: Permutation Sequence
• Difficulty: Hard
• Tag: Recursion Math

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"

Given n and k, return the kth permutation sequence.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

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

Solution

Python 3

from itertools import permutations


class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        arr = range(1, n + 1)
        res = list(permutations(arr))[k - 1]
        return "".join(map(lambda x: str(x), res))

---

最后更新: October 11, 2023