440. K-th Smallest in Lexicographical Order
和之前有一道386. Lexicographical Numbers 很像。不过直接套用的话会TLE。利用可能解区间的长度来快速衰减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
