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
| // @Title: 字典序的第K小数字 (K-th Smallest in Lexicographical Order)
// @Author: 15816537946@163.com
// @Date: 2022-03-24 00:03:30
// @Runtime: 0 ms
// @Memory: 1.8 MB
func getSteps(cur, n int) (steps int) {
first, last := cur, cur
for first <= n {
steps += min(last, n) - first + 1
first *= 10
last = last*10 + 9
}
return
}
func findKthNumber(n, k int) int {
cur := 1
k--
for k > 0 {
steps := getSteps(cur, n)
if steps <= k {
k -= steps
cur++
} else {
cur *= 10
k--
}
}
return cur
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
|