How does recursion help solve the Permutation Sequence problem?

Recursion simplifies the process of selecting each digit in the permutation by narrowing the choices at each step, using factorial-based division to determine the right number.

What is the time complexity of solving Permutation Sequence?

The time complexity is O(n), as the factorial approach allows for direct calculation of the permutation without generating all permutations.

Can we solve the Permutation Sequence problem iteratively?

Yes, it is possible to solve it iteratively by using factorial division in a loop to select numbers for each position in the sequence.

What is the key concept behind solving Permutation Sequence?

The key concept is using the factorial system to reduce the problem, and applying recursion or iteration to determine the kth permutation in the sequence.

How does GhostInterview assist with the Permutation Sequence problem?

GhostInterview helps you understand the recursive factorial approach and avoid common mistakes, making the process of solving the Permutation Sequence efficient and effective.

#60

Hard

auto_awesome数学·递归

LeetCode 题解工作台

排列序列

给出集合 [1,2,3,...,n] ，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123" "132" "213" "231" "312" "321" 给定 n 和 k ，返回第 k 个排列。示例 1：输入： n = 3, k…

数学递归

题目描述

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

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

"123"
"132"
"213"
"231"
"312"
"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!

lightbulb

解题思路

方法一：枚举

我们知道，集合 $[1,2,..n]$ 一共有 $n!$ 种排列，如果我们确定首位，那剩余位能组成的排列数量为 $(n-1)!$ 。

因此，我们枚举每一位 $i$ ，如果此时 $k$ 大于当前位置确定后的排列数量，那么我们可以直接减去这个数量；否则，说明我们找到了当前位置的数。

对于每一位 $i$ ，其中 $0 \leq i \lt n$ ，剩余位能组成的排列数量为 $(n-i-1)!$ ，我们记为 $fact$ 。过程中已使用的数记录在 vis 中。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        ans = []
        vis = [False] * (n + 1)
        for i in range(n):
            fact = 1
            for j in range(1, n - i):
                fact *= j
            for j in range(1, n + 1):
                if not vis[j]:
                    if k > fact:
                        k -= fact
                    else:
                        ans.append(str(j))
                        vis[j] = True
                        break
        return ''.join(ans)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of recursion and factorials.
question_mark
Check for the ability to optimize with factorials instead of brute force generation.
question_mark
Assess problem-solving by recursive breakdown of the sequence.

warning

常见陷阱

外企场景

error
Misunderstanding how factorials divide the problem into smaller sections, leading to incorrect permutation generation.
error
Failing to adjust the set of available numbers as elements are selected, causing incorrect positions.
error
Overcomplicating the solution by generating all permutations before selecting the kth one.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the nth permutation in lexicographic order of a different range of numbers.
arrow_right_alt
Use an iterative approach instead of recursion to find the kth permutation.
arrow_right_alt
Return the kth permutation for very large values of n by optimizing factorial computations.

help

常见问题

外企场景

继续练习

#50 Pow(x, n)#2 两数相加 #224 基本计算器