400. 第 N 位数字
400. 第 N 位数字
题目
Given an integer n
, return the nth
digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]
.
Example 1:
Input: n = 3
Output: 3
Example 2:
Input: n = 11
Output: 0
Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
Constraints:
1 <= n <= 2^31 - 1
题目大意
给你一个整数 n
,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]
中找出并返回第 n
位上的数字。
示例 1:
输入: n = 3
输出: 3
示例 2:
输入: n = 11
输出: 0
解释: 第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ,它是 10 的一部分。
提示:
1 <= n <= 2^31 - 1
解题思路
确定数字的位数:
- 计算在每个数字位数范围(1 ~ 9: 1 位、10 ~ 99: 2 位、100 ~ 999: 3 位等)中包含的数字总数,直到找到
n
位所在的范围。 - 对于
k
位数字,范围内的数字总个数为9 * 10^(k-1)
,且它们的总位数为k * 9 * 10^(k-1)
。
- 计算在每个数字位数范围(1 ~ 9: 1 位、10 ~ 99: 2 位、100 ~ 999: 3 位等)中包含的数字总数,直到找到
找到目标数字:
- 确定
n
所在的具体数字范围后,计算出是哪个数字以及在这个数字中的具体位置。 - 通过计算偏移量确定要返回的数字。
- 确定
复杂度分析
- 时间复杂度:
O(log_10 n)
,通过不断增加位数,最多会进行对数级别的计算。 - 空间复杂度:
O(1)
,只使用了常数级别的额外空间,存储了少量变量。
代码
/**
* @param {number} n
* @return {number}
*/
var findNthDigit = function (n) {
let digit = 1; // 当前位数
let count = 9; // 当前位数的数字总数
let start = 1; // 当前位数的起始数字
// 找到 n 所在的位数范围
while (n > count * digit) {
n -= count * digit;
digit++;
count *= 10;
start *= 10;
}
// 找到 n 所在的具体数字
const num = start + Math.floor((n - 1) / digit);
const index = (n - 1) % digit;
// 转换数字为字符串以获取具体的第 n 位数字
return Number(String(num)[index]);
};