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