0440：字典序的第K小数字（★★）

2016-03-15 约 374 字预计阅读 1 分钟次阅读

力扣第 440 题

题目

给定整数 n 和 k，返回 [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 <= 10⁹

分析

采用试填法，先考虑首位：
- 统计 [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

目录

0440：字典序的第K小数字（★★）

题目

分析

解答