【限时免费】20天拿下华为OD笔试之【回溯】2023B-第N个排序【欧弟算法】全网注释最详细分类最全的华为OD真题题解

【回溯】2023B-第N个排序

题目描述与示例

给定参数 n ，从 1 到 n 会有 n 个整数 1，2，3，...，n。这 n 个数字共有n!种排列，按大小顺序升序列出所有排列情况，并一一标记。当 n = 3 时，所有排列如下："123","132","213","231","312","321"。

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

输入

第一行为 n 第二行为 k n 的范围是 1 ~ 9 k 的范围是 1 ~ n!

输出

输出排列第 k 位置的数字

示例一

输入

3
3
1
2

输出

213
1

示例二

输入

2
2
1
2

输出

21
1

解题思路

这道题本质上是一道排列类型的回溯问题。具体过程和LC46. 全排列几乎完全一致。

注意本题可以进行剪枝操作，即无需计算所有排列，只需要计算前k个排列即可。

代码

# 题目：2023B-第N个排列
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：回溯
# 代码看不懂的地方，请直接在群上提问


# 输入n和k
n = int(input())
k = int(input())

# 用于记录当前已经得到了几个全排列的变量cnt
cnt = 0
ans = ""

usedList = [False] * (n+1)

def dfs(path, usedList, k, n):
    # cnt和ans均需要声明为全局变量
    global cnt, ans
    # 如果path的长度等于n，那么得到了一个全排列
    if len(path) == n:
        # 已获得的全排列的数目+1
        cnt += 1
        # 如果已经获得了第k个排列，那么得到了答案
        if cnt == k:
            ans = "".join([str(num) for num in path])
        return
    # 如果path的小于n，进行递归
    else:
        for i in range(1, n+1):
            # 如果i尚未使用过，那么可以进行递归
            if usedList[i] == False:
                # 状态更新：usedList[i]改为True，将i加入当前path
                usedList[i] = True
                path.append(i)
                # 回溯
                dfs(path, usedList, k, n)
                # 回滚：usedList[i]改为False，将i从当前path中删除
                usedList[i] = False
                path.pop()
                # 这里可以进行剪枝，虽然可以不加，但是尽量加上
                # 即如果已经找到了第k个排列，那么无需进行后续的回溯
                if cnt == k:
                    return

# 调用递归函数的入口，最开始path为空列表
dfs([], usedList, k, n)
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

时空复杂度

时间复杂度：O(k)。需要计算得到前k种排列。

空间复杂度：O(N)。usedList所占空间。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多