跳至主要內容

440. 字典序的第K小数字


440. 字典序的第K小数字open in new window

🔴   🔖  字典树  🔗 力扣open in new window LeetCodeopen in new window

题目

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Example 1:

Input: n = 13, k = 2

Output: 10

Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Example 2:

Input: n = 1, k = 1

Output: 1

Constraints:

  • 1 <= k <= n <= 10^9

题目大意

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

解题思路

思路一:字典树计数

直接构建从 1n 的所有数字并进行排序的时间复杂度较高,因此需要更高效的算法,可以利用字典序的树状结构。

我们可以将数字可视化为字典顺序树:

  • 根节点为 1,其子节点为 10、11、12 ... 19
  • 根节点为 2,其子节点为 20、21 ... 29 等等;

根据这种结构,问题变成了遍历字典树,计算每个节点下有多少个数字。

使用一个计数函数 getReqNum(a, n) 来计算字典树中以 a 为前缀的数字有多少个,考虑最多 n 个数字。

一旦我们知道以 a 为前缀的数字有多少个,我们就可以决定是跳过 a(如果计数小于 k)移动到下一个兄弟节点 a + 1,还是深入 a 的子树中。

复杂度分析

  • 时间复杂度O(K log n),每次查找最多需要 O(log n) 的时间(因为在树的层级中),对于 K 次查找,总体复杂度是 O(K log n)
  • 空间复杂度O(1),因为使用一些变量来跟踪当前数字,并且除了整数变量之外不使用任何其他数据结构。

思路二:字典树(超时)

思路一的方式并没有真的构建字典树,只是利用了字典树的结构,来计算每个节点下有多少个数字。

思路二尝试了真的构建一个字典树,然后深度优先遍历字典树,找到第 K 个数字。

这种做法无法跑通所有的测试用例,遇到很大的数字时会超时,但是仍然可以尝试写一写,作为一种练习。

  1. 构建字典树

    • 初始化一个空的字典树(Trie)。
    • 使用一个循环遍历从 1n 的所有整数,将它们的每一位字符插入字典树中。对于每个数字,将其转换为字符串,然后逐位插入字典树。
    • 在每个数字的末尾标记 isEndtrue,表示这个数字的结尾。
  2. 前序遍历查找前 K 个数

    • 使用深度优先搜索(DFS)遍历字典树,从根节点开始,构建一个字符串 str 来表示当前路径。
    • 如果当前节点标记为 isEnd,说明找到了一个有效的数字,将其添加到结果数组 track 中。
    • 遍历当前节点的所有子节点,继续深度优先搜索。
    • 直到找到 K 个数字或者没有更多节点可以遍历。
  3. 返回结果

    • 最后,从 track 数组中返回第 K 个数字(即数组的最后一个元素),将其转换为数字类型。

复杂度分析

  • 时间复杂度O(n * log(n))

    • 在构建字典树的过程中,对于每个数字 1n,最多需要插入 log(n) 个字符,因此构建字典树的时间复杂度为 O(n * log(n))
    • 在前序遍历查找 K 个数的过程中,遍历的时间复杂度取决于字典树的结构,但在最坏情况下也可以认为是 O(n)
    • 因此,总体时间复杂度为 O(n * log(n))
  • 空间复杂度O(n * log(n))

    • 字典树的空间复杂度取决于存储的数字数量和其字符的长度。在最坏情况下,字典树的空间复杂度为 O(n * log(n))
    • 另外,结果数组 track 的大小最多为 K,因此额外的空间复杂度为 O(K)
    • 综合来看,空间复杂度为 O(n * log(n))

代码

字典树计数
var findKthNumber = function (n, k) {
	const getReqNum = (first, n) => {
		let gap = 0,
			last = first + 1;
		while (first <= n) {
			gap += Math.min(n + 1, last) - first;
			first *= 10;
			last *= 10;
		}
		return gap;
	};

	let num = 1;
	let i = 1;

	while (i < k) {
		let req = getReqNum(num, n);
		if (i + req <= k) {
			i += req;
			num++;
		} else {
			i++;
			num *= 10;
		}
	}

	return num;
};

相关题目

题号标题题解标签难度
2376统计特殊整数open in new window数学 动态规划