第 N 位数字
难度:
标签:
题目描述
给你一个整数 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 <= 231 - 1
代码结果
运行时间: 20 ms, 内存: 16.5 MB
// Java Stream solution
// The problem can also be solved using Java Streams, though it may not be as straightforward as the loop approach.
// Approach:
// 1. We generate the numbers and concatenate them as strings.
// 2. Using Stream, we find the nth digit.
import java.util.stream.Stream;
public class Solution {
public int findNthDigit(int n) {
return Stream.iterate(1, i -> i + 1)
.map(Object::toString)
.flatMapToInt(String::chars)
.map(c -> c - '0')
.skip(n - 1)
.findFirst()
.getAsInt();
}
}
解释
方法:
这个题解的思路是先确定第 n 位数字所在的数字的位数,然后确定该数字,最后确定该数字的第 n 位。具体来说:
1. 首先通过 while 循环确定第 n 位所在的数字的位数 digit,同时更新剩余的 n。
2. 然后根据剩余的 n 和位数 digit 计算出第 n 位所在的数字 num。
3. 最后将 num 转为字符串,并取出第 (n-1) % digit 个字符,转换为整数作为结果返回。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解的 while 循环中,你是如何确定变量 count 的计算公式 'count = 9 * start * digit',它代表了什么意义?
▷🦆
为什么在计算 num 时使用了 'start + (n - 1) // digit' 这个公式,这里的 (n - 1) // digit 是如何定位到正确的数字的?
▷🦆
题解中提到,返回结果是 'int(str(num)[(n - 1) % digit])',为什么这里要使用 (n - 1) % digit 来取得数字的具体哪一位?
▷🦆
在题解中没有明确提到如何处理 n 减去 count 后可能的边界情况(如 n 正好减到0或变成负数),这个算法如何确保最后的 n 是有效的?
▷