440. 字典序的第K小数字
440. 字典序的第K小数字
题目
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 个数字。
这种做法无法跑通所有的测试用例,遇到很大的数字时会超时,但是仍然可以尝试写一写,作为一种练习。
构建字典树:
- 初始化一个空的字典树(Trie)。
- 使用一个循环遍历从
1
到n
的所有整数,将它们的每一位字符插入字典树中。对于每个数字,将其转换为字符串,然后逐位插入字典树。 - 在每个数字的末尾标记
isEnd
为true
,表示这个数字的结尾。
前序遍历查找前 K 个数:
- 使用深度优先搜索(DFS)遍历字典树,从根节点开始,构建一个字符串
str
来表示当前路径。 - 如果当前节点标记为
isEnd
,说明找到了一个有效的数字,将其添加到结果数组track
中。 - 遍历当前节点的所有子节点,继续深度优先搜索。
- 直到找到 K 个数字或者没有更多节点可以遍历。
- 使用深度优先搜索(DFS)遍历字典树,从根节点开始,构建一个字符串
返回结果:
- 最后,从
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 | 统计特殊整数 | 数学 动态规划 |