440. 字典序的第K小数字

🔴   🔖  字典树  🔗 LeetCode

题目

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

题目大意

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

解题思路

思路一：字典树计数

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

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

• 根节点为 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）。
   • 使用一个循环遍历从 1 到 n 的所有整数，将它们的每一位字符插入字典树中。对于每个数字，将其转换为字符串，然后逐位插入字典树。
   • 在每个数字的末尾标记 isEnd 为 true，表示这个数字的结尾。

2. 前序遍历查找前 K 个数：

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

3. 返回结果：

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

复杂度分析

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

  • 在构建字典树的过程中，对于每个数字 1 到 n，最多需要插入 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;
};

字典树（超时）

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function (n, k) {
	let trie = {},
		i = 1;

	// 构建字典树
	while (i <= n) {
		let temp = trie;
		for (let char of '' + i) {
			if (!temp[char]) {
				temp[char] = {};
			}
			temp = temp[char];
		}
		temp.isEnd = true;
		i++;
	}

	// 前序遍历查找字典树中的前 K 个数
	let track = [];
	const dfs = (node, str) => {
		if (!node || track.length == k) {
			return;
		}
		if (node.isEnd) {
			track.push(str);
		}
		for (let key of Object.keys(node)) {
			if (key !== 'isEnd') {
				dfs(node[key], str + key);
			}
		}
	};
	dfs(trie, '');

	// 返回第 K 个数
	return Number(track[track.length - 1]);
};

相关题目

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