目录

0440:字典序的第K小数字(★★)

力扣第 440 题

题目

给定整数 nk,返回 [1, n] 中字典序第 k 小的数字。

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

提示:

  • 1 <= k <= n <= 109

相似问题:

分析

  • 采用试填法,先考虑首位:
    • 统计 [1,n] 中首位 1 的个数 w
    • 如果 w>=k,首位即是 1
    • 如果 w<k,更新 k-=w,继续试填 2
    • 依此类推确定首位为 a
  • 接着考虑第二位:
    • 如果 k=1,说明 a 即为所求,没有第二位
    • 否则,更新 k-=1,第二位试填 0
    • 接着要统计 [1,n] 中前缀为 a0 的个数
    • 后面依此类推
  • 综上,每一步试填需要计算 [1,n] 中前缀 p 的个数
    • 可以采用分段计数
    • 分别计算 p 后面跟 0 位、1 位、2 位等的个数即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def cal(p):
            res, w = 0, 1
            while p<=n:
                res += min(w,n-p+1)
                p *= 10
                w *= 10
            return res

        res = 1
        while k>1:
            w = cal(res)
            if w < k:
                k -= w
                res += 1
            else:
                k -= 1
                res *= 10
        return res

38 ms