刷题笔记合集🔗

第k个排列

题目描述

给定参数 ,从 到 会有 个整数:,这 个数字共有 种排列。

按大小顺序升序列出所有排列情况,并一一标记,当 时,所有排列如下:

、、、、、

给定 和 ,返回第 个排列。

输入格式

第一行包含两个正整数 和 ,表示给定的参数。

输出格式

输出排在第 位置的数字。

样例输入1

3 3

样例输出1

213

样例输入2

2 2

样例输出2

21

样例解释

样例1	的排列有 、、,那么第三位就是 。
样例2	的排列有 、,那么第二位置的为 。

数据范围

题解

DFS

从左到右,每个位置都尝试填入一个数字。对于第一个位置,有 种选择;当第一个数字确定后,第二个位置我们就有 种选择;依此类推,最后一个位置只有一种选择。

这就是一个典型的DFS过程。可以用递归来实现,每次递归选择一个数字填入当前位置,然后继续递归填入下一个位置,直到填完所有位置,产生了一个排列。

在递归的过程中,用一个变量 来记录当前已经产生的排列数。每产生一个新的排列, 就加 。当 等于 时,就说明已经得到了第 个排列,可以将其返回。

为了避免产生重复的排列,可以用一个布尔数组 来标记每个数字是否已经被使用过。每次填入一个数字,就将其标记为已使用;回溯时,再将其标记为未使用。

这个暴力DFS的时间复杂度是 ,因为我们需要生成所有的排列。但是由于 的范围很小(不超过 ), 不会很大,所以这个复杂度是可以接受的。

空间复杂度是 ,主要是递归栈的开销。

参考代码

• Python

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        def dfs(cur, count):
            """
            cur: 当前已经产生的排列(字符串形式)
            count: 当前已经产生的排列数
            """
            nonlocal k, res
            # 如果已经产生了 k 个排列,就可以返回了
            if count == k:
                res = cur
                return
            # 依次尝试填入每个未使用的数字    
            for i in range(1, n+1):
                if not used[i]:
                    used[i] = True
                    dfs(cur + str(i), count + 1)
                    # 回溯
                    used[i] = False
        
        # 初始化结果和标记数组            
        res = ''
        used = [False] * (n + 1)
        # 开始 DFS
        dfs('', 0)
        return res

• C

char* getPermutation(int n, int k) {
    // 初始化结果字符串和标记数组
    char* res = (char*)malloc(sizeof(char) * (n + 1));
    res[n] = '\0';
    int used[n + 1];
    memset(used, 0, sizeof(used));
    
    // 定义 DFS 函数
    void dfs(char* cur, int count) {
        // 如果已经产生了 k 个排列,就可以返回了
        if (count == k) {
            strcpy(res, cur);
            return;
        }