leetcode
leetcode 351 ~ 400
第 N 位数字

第 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',它代表了什么意义?
在题解中,变量 'count' 的计算公式 'count = 9 * start * digit' 是用来确定在当前位数 'digit' 下所有数字的总位数。这里的 'start' 表示该位数下的第一个数字(如:1, 10, 100 等),而 'digit' 表示当前数字的位数(如:1位数、2位数)。因此,从 'start' 开始的前 9 个数(如:1 到 9, 10 到 99, 100 到 999 等)包含的总位数就是 '9 * start * digit'。这个公式帮助算法快速跳过大量数字,直到找到包含第 n 位的具体数字。
🦆
为什么在计算 num 时使用了 'start + (n - 1) // digit' 这个公式,这里的 (n - 1) // digit 是如何定位到正确的数字的?
在计算变量 'num' 时使用的公式 'start + (n - 1) // digit' 是为了找出具体包含第 n 位的整数。这里的 'start' 是当前位数的第一个数字,而 '(n - 1) // digit' 是计算从 'start' 开始后应该跳过多少个整数才能到达包含第 n 位的数字。这个公式的含义是在已知每个数字占用 'digit' 个位置的情况下,计算并跳过前面的完整数字,直接定位到包含目标位的数字。
🦆
题解中提到,返回结果是 'int(str(num)[(n - 1) % digit])',为什么这里要使用 (n - 1) % digit 来取得数字的具体哪一位?
题解中使用 '(n - 1) % digit' 是为了定位在数字 'num' 中第 n 位所在的具体位置。由于 'num' 是由多个数字位组成,'digit' 是每个数字的位数。因此,'(n - 1) % digit' 计算的是在数字 'num' 中,第 n 位是从左到右的第几位(从0开始计数)。这样就能精确地提取出 'num' 的特定一位,转换成整数后作为结果返回。
🦆
在题解中没有明确提到如何处理 n 减去 count 后可能的边界情况(如 n 正好减到0或变成负数),这个算法如何确保最后的 n 是有效的?
在题解的 while 循环中,每次循环都会检查 'n > count' 来决定是否继续减去 'count'。这个循环保证了只有当 'n' 大于当前 'count' 时,才会进行减法操作。一旦 'n' 不大于 'count',循环就会停止。因此,'n' 不会减到0或变负。在循环结束时,'n' 会是一个有效的、正好指向所需数字位的正整数,确保算法可以正确地继续计算 'num' 以及从 'num' 中取得具体的一位数字。

相关问题