Leetcode 440. 字典序的第K小数字

1.题目基本信息

1.1.题目描述

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

1.2.题目地址

https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/

2.解题方法

2.1.解题思路

字典树思路

记第i小结点为ni，ni子树中节点数为steps，由于进行的是前序遍历，则如果k-i>=steps，第k小的节点一定不在ni的子树中，则需要往ni的右侧相邻兄弟节点进行遍历；如果k-i<steps，则第k小的节点一定在ni的子树中，则节点往ni的最左侧子节点走；

重复上面两步，更新i，直到i=k，即得到题解。（注：这里不用担心以9结尾的数字没有兄弟节点的问题，通过模拟知道不会走到这一步）

2.2.解题步骤

第一步，构建维护变量。k维护k-i的值，即当前节点到第k小结点的距离；val维护第i小的节点的值

第二步，构建getSteps函数，获取值为val的节点子树中节点数，使用广搜的方法

第三步，记steps=getSteps(val)，如果k>=steps，则第k小的节点不在当前节点的子树中，节点往当前节点的右相邻兄弟节点走，更新val=val+1，更新k=k-steps；如果k<steps，则第k小的节点一定在当前节点的子树中，节点往当前节点的最左侧子节点走，更新val=val*10，更新k=k-1

3.解题代码

python代码

class Solution:def findKthNumber(self, n: int, k: int) -> int:# 思路：字典树思路。记第i小结点为ni，ni子树中节点数为steps，由于进行的是前序遍历，则如果k-i>=steps，第k小的节点一定不在ni的子树中，则需要往ni的右侧相邻兄弟节点进行遍历；如果k-i<steps，则第k小的节点一定在ni的子树中，则节点往ni的最左侧子节点走；重复上面两步，更新i，直到i=k，即得到题解。（注：这里不用担心以9结尾的数字没有兄弟节点的问题，通过模拟知道不会走到这一步）# 第一步，构建维护变量。k维护k-i的值，即当前节点到第k小结点的距离；val维护第i小的节点的值k -= 1val = 1# 第二步，构建getSteps函数，获取值为val的节点子树中节点数，使用广搜的方法def getSteps(nodeVal:int) -> int:steps, first, last = 0, nodeVal, nodeValwhile first <= n:steps += min(last, n) - first + 1first = first * 10last = last * 10 + 9return steps# 第三步，记steps=getSteps(val)，如果k>=steps，则第k小的节点不在当前节点的子树中，节点往当前节点的右相邻兄弟节点走，更新val=val+1，更新k=k-steps；如果k<steps，则第k小的节点一定在当前节点的子树中，节点往当前节点的最左侧子节点走，更新val=val*10，更新k=k-1while k > 0:steps = getSteps(val)if k >= steps:val += 1k -= stepselse:val *= 10k -= 1return val

4.执行结果