Участник:Plague rat/K-th Smallest in LexOrder

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        if n < 10:
            return k
 
        ans = 1
        k -= 1
        while (k > 0):
            step = 0
            leftBoundRank = ans
            rightBoundRank = ans + 1;
            while (leftBoundRank <= n):
                step += min(n + 1, rightBoundRank) - leftBoundRank
                leftBoundRank *= 10
                rightBoundRank *= 10
 
            if (step <= k):
                ans += 1
                k -= step
            else:
                ans *= 10
                k -= 1
 
        return ans