440.md

440 K-th Smallest in Lexicographical Order

Description

link

---

Solution

• See Code

---

Code

Complexity T : O((logn)^2) M : -

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        result = 1;
        k -= 1
        while k > 0:
            count = 0 # 区间记数
            interval = [result, result+1] # 当前区间
            while interval[0] <= n: # 区间下限没有超过n
                count += (min(n+1, interval[1]) - interval[0]) # 当前区间总数目，当n在其中时，取到n为止
                interval = [10*interval[0], 10*interval[1]] # [1, 2] -> [10, 20] [100, 200] -> [1000, 2000] 按照字典排序
            
            if k >= count: # k不在上述遍历的范围内，减掉对应的数目即可
                result += 1 # 基准数字往前移动一位，寻找字典排序的下面的区间
                k -= count
            else: # k在上述范围内，需要具体细化找到k的位置
                result *= 10 # 基准数字扩大10倍，寻找当前范围内的细化位置
                k -= 1 # 每扩大10倍，k往后移动一位，因为其实只去掉了一个数字
        return result