Re: [閒聊] 每日leetcode
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--
for k > 0 {
step := cnt(i, n)
if step <= k {
k -= step
i++
} else {
i *= 10
k--
}
}
return i
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.1.65 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726987582.A.503.html
推
09/22 14:48,
1年前
, 1F
09/22 14:48, 1F
→
09/22 14:50,
1年前
, 2F
09/22 14:50, 2F
→
09/22 15:02,
1年前
, 3F
09/22 15:02, 3F
討論串 (同標題文章)
完整討論串 (本文為第 891 之 1548 篇)：