440. K-th Smallest in Lexicographical Order
给n跟k两个整数
请回传在[1:n]间字母顺第k小的数字
思路:
跟昨天那题差不多
不过这题范围比较大
所以如果从头开始找会TLE
假设n是8xxxx的一个数字
那1开头的数字会有1+10+100+1000+10000=11111个
可以用这个规则来加速搜寻
假设i开头的数字有steps个
那会有三种情况
(1)steps<k
这种情况把k-steps，接着i+1继续算
(2)steps>k
这种情况代表答案是i开头的数字
把k-1(这边的1是i)
接着继续缩小范围把i*10下去继续找
(3)steps==k
找到答案回传i+1
golang code :
func cnt(num, n int) int {
steps := 0
first, last := num, num
for first <= n {
steps += min(last, n) - first + 1
first *= 10
last = last*10 + 9
}
return steps
}
func findKthNumber(n int, k int) int {
i := 1
k