8.22 - hard - 85

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