440. K-th Smallest in Lexicographical Order
和之前有一道386. Lexicographical Numbers 很像兔院。不過直接套用的話會TLE格侯。利用可能解區(qū)間的長度來快速衰減K有點log的解法
TLE版本
class Solution(object):
def findKthNumber(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
res = [1]
while len(res) < n:
new = res[-1] * 10
while new > n:
new /= 10
new += 1
while new % 10 == 0:
new /= 10
res.append(new)
return res[k-1]
class Solution(object):
def findKthNumber(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
result = 1;
k -= 1
while k > 0:
count = 0
interval = [result, result+1]
while interval[0] <= n:
count += (min(n+1, interval[1]) - interval[0])
interval = [10*interval[0], 10*interval[1]]
if k >= count:
result += 1
k -= count
else:
result *= 10
k -= 1
return result
