题目

某班级学号记录系统发生错乱，原整数学号序列 [1,2,3,4,…] 分隔符丢失后变为 1234… 的字符序列。请实现一个函数返回该字符序列中的第 k 位数字。

示例 1：

输入：k = 5
输出：5

示例 2：

输入：k = 12
输出：1
解释：第 12 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 1 ，它是 11 的一部分。

提示：

0 <= k < 231

代码

class Solution {
public int findKthNumber(int n) {
if(n == 0){
return 0;
}

    long bit = 1;int i = 1;long count = 9;while(count < n){n = (int)(n - count);bit = bit * 10;i++;count = bit * i * 9;}// 确定是在这个区间的哪个数long num = bit + (n - 1) / i;// 确定在 Num 的那个字符int index = (n - 1) % i + 1;int res = (int)(num / Math.pow(10, i - index)) % 10;return res;
}

}
时间复杂度：O(logn)
额外空间复杂度：O(1)