Leetcode 440. 字典序的第K小数字

题目描述：

给定整数 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 <= 109

思路

通过观察字典序的排列可以发现以下规律：

• 以i+1开头的字典序肯定大于以i开头的
• i*10 => 字典序+1
• i+1 => 字典序+(i+1作为前缀的最小值 - i作为前缀的最小值)

要找到在[1,n]中第k小的数字，我们肯定需要从以i作为前缀的开始数，首先需要计算出以i为前缀的个数，以i为前缀的个数即：以i+1为前缀的最小值-以i为前缀的最小值，且这些值都必须小于n。

找到以i为前缀的个数count后，有两种情况：

• k>count，说明以i为前缀的个数不够，还需要继续去找i+1的，k-=count，将i+1；
• k<=count，则说明第k小的数字就是以i开头的，那么通过将i*10将字典序+1，然后重复上面的步骤就可以找出第k小字典序的数字了。

代码

impl Solution {
    pub fn find_kth_number(n: i32, k: i32) -> i32 {
        let (mut k, mut cur, n) = ((k - 1) as i64, 1 as i64, n as i64);
        while k > 0 {
            let (mut count, mut first, mut last) = (0, cur, cur + 1);
            while first <= n {
                count += last.min(n + 1) - first;
                first *= 10;
                last *= 10;
            }
            if count <= k {
                cur += 1;
                k -= count;
            } else {
                cur *= 10;
                k -= 1;
            }
        }
        cur as i32
    }
}