题目描述
给定整数 n
和 k
,返回 [1, n]
中字典序第 k
小的数字。
样例
输入:n = 13, k = 2
输出:10
解释:字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。
输入:n = 1, k = 1
输出:1
限制
1 <= k <= n <= 10^9
算法
(数位统计) $O(\log^2 n)$
- 我们从最终答案的前缀开始枚举,初始时前缀为 1,这也是字典序最小的数字。
- 假设当前的前缀为
prefix
,且我们需要找这个前缀下的第k
小的数字。 - 如果
k == 1
,则当前前缀就是答案。否则我们计算这个前缀能组成数字的个数,记为sz
。 - 若
k > sz
,则说明这个答案不是以这个前缀为开头的数字,令k -= sz
,且前缀最后一位增加 1 (prefix++
)。重新寻找在新前缀下的新的第k
个。 - 否则,说明答案就是以这个前缀构成的,
k--
,因为这个前缀本身占用了一个位置,然后prefix = prefix * 10
,即往后增加一位 0。 - 这里简单说下如何求以某个前缀
prefix
构成的数字的个数:若prefix * 10
的数字位数小于n
的数字位数,则prefix_0, prefix_1, ..., prefix_9
都可以构成答案,接着若prefix * 100
的位数小于n
的数字位数,prefix_00, prefix_01, ..., prefix_99
也都是答案。当最后与prefix_00...0
再加一个0
就会大于n
时,需要根据n
的上限补全当前位数下能构成数字的个数。
时间复杂度
- 计算以某个前缀构成的数字个数的时候需要 $O(\log n)$ 的时间。
- 每一位最多枚举 10 个数字,故总时间复杂度为 $O(\log^2 n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
private:
int calc(int prefix, int n) {
int tot = 0;
LL t = prefix, k = 1;
while (t * 10 <= n) {
tot += k;
k *= 10;
t *= 10;
}
if (n - t < k)
tot += n - t + 1;
else
tot += k;
return tot;
}
public:
int findKthNumber(int n, int k) {
int prefix = 1;
while (k > 1) {
int sz = calc(prefix, n);
if (k > sz) {
k -= sz;
prefix++;
} else {
k--;
prefix = prefix * 10;
}
}
return prefix;
}
};
不过 这行好像有问题,if (t <= n) { // 此时 t 一定和 n 数字的位数相同。
比如 n=23456, k = 22224
prefix在枚举到3的时候,t=3000,比n少了1位。
已修正,去掉了这个判断,不会影响答案的正确性
比yxc老师的做法更清晰,👍
感谢 感谢 这个解析是真的超级清楚
哈哈 看懂了