字典序的第K小数字Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。
示例 1:
输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
示例 2:
输入: n = 1, k = 1
输出: 1
提示:
1 <= k <= n <= 109
# 思路
/*
本质是一个10叉树的先序遍历,找到按照先序遍历的第k个节点
为什么是先序遍历?这个由字典序的性质决定:[1,10,100,1000,1001]
假设相同位数的数字在10叉树的同一层上,那么就是先序遍历就是字典序排列
从cur=1开始进行遍历,先计算的以cur为根的且<=n的节点个数nodes
若nodes<=k,说明以cur开头的合格节点数不够,cur应该向右走:cur++
若nodes>k,说明以cur开头的合格节点数足够,cur应该向下走:cur*=10
*/
// 首先遍历以1开头大的数字
// 由于cur可能会很大,因此int可能计算过程中会溢出,用long类型
# 解法
class Solution {
public int findKthNumber(int n, int k) {
/*
本质是一个10叉树的先序遍历,找到按照先序遍历的第k个节点
为什么是先序遍历?这个由字典序的性质决定:[1,10,100,1000,1001]
假设相同位数的数字在10叉树的同一层上,那么就是先序遍历就是字典序排列
从cur=1开始进行遍历,先计算的以cur为根的且<=n的节点个数nodes
若nodes<=k,说明以cur开头的合格节点数不够,cur应该向右走:cur++
若nodes>k,说明以cur开头的合格节点数足够,cur应该向下走:cur*=10
*/
// 首先遍历以1开头大的数字
// 由于cur可能会很大,因此int可能计算过程中会溢出,用long类型
long cur = 1;
// 因为1遍历了,因此k--
k--;
// 当且仅当k>0(还未遍历到第k个的时候)循环
while(k > 0) {
// 获取以cur开头的子节点合格(<=n)数目nodes
int nodes = getNodes(n, cur);
// 若nodes<=k的话说明把这nodes个节点分完都还没到k
if(nodes <= k) {
// cur向右走
cur++;
// 抵消掉nodes个节点
k -= nodes;
}else {
// 若nodes>k的话说明把nodes个节点够分
// cur往下走
cur *= 10;
// 将cur计算进k
k--;
}
}
// 最后cur会停留在第k小的数上
return (int)cur;
}
/*
计算[1,n]内以cur为根(开头)的节点个数
*/
private int getNodes(int n, long cur) {
// next表示cur右边的数,此时cur=10,next=11
long next = cur + 1;
// 统计合格的节点个数
long totalNodes = 0;
// 当cur<=n时可以进入循环
while(cur <= n) {
// 这里是最关键的一步:当n不在cur层时,该层有效节点数目为next - cur(全部都要了)
// 当n在cur层时,该层有效节点数目为n - cur + 1(要一部分)
// 统一起来就是取最小值
totalNodes += Math.min(n - cur + 1, next - cur);
// cur与next均向下计算
cur *= 10;
next *= 10;
}
return (int)totalNodes;
}
}
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
50
51
52
53
54
55
56
57
58
59
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
50
51
52
53
54
55
56
57
58
59
# 总结
- 分析出几种情况，然后分别对各个情况实现
