江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第400题：第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 ，它

博客摘要：本文深入解析LeetCode第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 <= 2^31 - 1

题目链接：LeetCode 400. 第N位数字

解题思路

这道题的关键是找到数字序列的规律，然后通过数学计算直接定位到第N位数字，而不是暴力枚举。

数字序列分析

无限整数序列的构成：

  • 1位数：1-9，共9个数字，占用9×1=9位
  • 2位数：10-99，共90个数字，占用90×2=180位
  • 3位数：100-999，共900个数字，占用900×3=2700位
  • k位数：10^(k-1) 到 10^k-1，共9×10^(k-1)个数字，占用9×10^(k-1)×k位

三步解题法

  1. 确定位数：找到第N位数字属于几位数
  2. 确定数字：在该位数范围内找到具体是哪个数字
  3. 确定位置：在该数字中找到是第几位

算法原理

详细推导过程

第一步：确定位数

累计位数计算：
1位数：9位
2位数：9 + 180 = 189位
3位数：189 + 2700 = 2889位
...

第二步：确定数字
假设第N位在k位数中，设前面所有位数的总和为prevCount：

  • 在k位数中的位置：n - prevCount
  • 属于第几个k位数：(n - prevCount - 1) // k
  • 具体数字：10^(k-1) + (n - prevCount - 1) // k

第三步：确定位置

  • 在该数字中的位置：(n - prevCount - 1) % k

复杂度分析

  • 时间复杂度：O(log n)

    • 最多需要循环log₁₀(n)次来确定位数
    • 每次循环都是常数时间操作

  • 空间复杂度：O(1)

    • 只使用常数个额外变量

图解思路

序列：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
位置：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...

示例：n = 11
第11位是数字10中的'0'

分析过程：
1. 1位数：1-9，占用9位（位置1-9）
2. 第11位在2位数中（11 > 9）
3. 在2位数中的位置：11 - 9 = 2
4. 属于第几个2位数：(2-1) // 2 = 0（第0个）
5. 具体数字：10 + 0 = 10
6. 在数字10中的位置：(2-1) % 2 = 1（第1位，即'0'）

分段计算表

位数 数字范围 数字个数 总位数 累计位数
1 1-9 9 9×1=9 9
2 10-99 90 90×2=180 189
3 100-999 900 900×3=2700 2889
k 10^(k-1) ~ 10^k-1 9×10^(k-1) 9×10^(k-1)×k …

代码实现

C# 实现

public class Solution {
    public int FindNthDigit(int n) {
        // 第一步：确定第n位数字的位数
        int digits = 1;      // 当前考虑的位数
        long count = 9;      // 当前位数的数字个数
        long start = 1;      // 当前位数的起始数字
        
        // 找到第n位数字属于几位数
        while (n > digits * count) {
            n -= (int)(digits * count);
            digits++;
            count *= 10;
            start *= 10;
        }
        
        // 第二步：确定具体是哪个数字
        long number = start + (n - 1) / digits;
        
        // 第三步：确定是该数字的第几位
        int digitIndex = (n - 1) % digits;
        
        // 提取该位数字
        string numberStr = number.ToString();
        return numberStr[digitIndex] - '0';
    }
    
    // 另一种不使用字符串的实现
    public int FindNthDigitV2(int n) {
        int digits = 1;
        long count = 9;
        long start = 1;
        
        while (n > digits * count) {
            n -= (int)(digits * count);
            digits++;
            count *= 10;
            start *= 10;
        }
        
        long number = start + (n - 1) / digits;
        int digitIndex = (n - 1) % digits;
        
        // 不使用字符串，直接计算第digitIndex位数字
        for (int i = 0; i < digits - 1 - digitIndex; i++) {
            number /= 10;
        }
        
        return (int)(number % 10);
    }
}

Python 实现

class Solution:
    def findNthDigit(self, n: int) -> int:
        # 第一步：确定第n位数字的位数
        digits = 1      # 当前考虑的位数
        count = 9       # 当前位数的数字个数
        start = 1       # 当前位数的起始数字
        
        # 找到第n位数字属于几位数
        while n > digits * count:
            n -= digits * count
            digits += 1
            count *= 10
            start *= 10
        
        # 第二步：确定具体是哪个数字
        number = start + (n - 1) // digits
        
        # 第三步：确定是该数字的第几位
        digit_index = (n - 1) % digits
        
        # 提取该位数字
        return int(str(number)[digit_index])
    
    def findNthDigitV2(self, n: int) -> int:
        # 不使用字符串的版本
        digits = 1
        count = 9
        start = 1
        
        while n > digits * count:
            n -= digits * count
            digits += 1
            count *= 10
            start *= 10
        
        number = start + (n - 1) // digits
        digit_index = (n - 1) % digits
        
        # 计算第digit_index位数字（从左到右，0-based）
        for _ in range(digits - 1 - digit_index):
            number //= 10
        
        return number % 10
    
    def findNthDigitV3(self, n: int) -> int:
        # 使用数学公式直接计算
        digits = 1
        count = 9
        start = 1
        
        while n > digits * count:
            n -= digits * count
            digits += 1
            count *= 10
            start *= 10
        
        number = start + (n - 1) // digits
        digit_index = (n - 1) % digits
        
        # 使用10的幂来提取特定位
        return (number // (10 ** (digits - 1 - digit_index))) % 10

C++ 实现

class Solution {
public:
    int findNthDigit(int n) {
        // 第一步：确定第n位数字的位数
        int digits = 1;          // 当前考虑的位数
        long long count = 9;     // 当前位数的数字个数
        long long start = 1;     // 当前位数的起始数字
        
        // 找到第n位数字属于几位数
        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            start *= 10;
        }
        
        // 第二步：确定具体是哪个数字
        long long number = start + (n - 1) / digits;
        
        // 第三步：确定是该数字的第几位
        int digitIndex = (n - 1) % digits;
        
        // 提取该位数字
        string numberStr = to_string(number);
        return numberStr[digitIndex] - '0';
    }
    
    // 不使用字符串的版本
    int findNthDigitV2(int n) {
        int digits = 1;
        long long count = 9;
        long long start = 1;
        
        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            start *= 10;
        }
        
        long long number = start + (n - 1) / digits;
        int digitIndex = (n - 1) % digits;
        
        // 计算第digitIndex位数字
        for (int i = 0; i < digits - 1 - digitIndex; i++) {
            number /= 10;
        }
        
        return number % 10;
    }
    
    // 使用pow函数的版本
    int findNthDigitV3(int n) {
        int digits = 1;
        long long count = 9;
        long long start = 1;
        
        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            start *= 10;
        }
        
        long long number = start + (n - 1) / digits;
        int digitIndex = (n - 1) % digits;
        
        // 使用pow函数提取特定位
        return (number / (long long)pow(10, digits - 1 - digitIndex)) % 10;
    }
};

执行结果

C# 实现

  • 执行用时：16 ms（字符串版本）/ 20 ms（数学版本）
  • 内存消耗：26.8 MB（字符串版本）/ 26.5 MB（数学版本）

Python 实现

  • 执行用时：32 ms（字符串版本）/ 36 ms（数学版本）
  • 内存消耗：16.8 MB（字符串版本）/ 16.6 MB（数学版本）

C++ 实现

  • 执行用时：0 ms（字符串版本）/ 0 ms（数学版本）
  • 内存消耗：6.1 MB（字符串版本）/ 5.8 MB（数学版本）

性能对比

版本 语言 执行用时 内存消耗 特点
数学版本 C++ 0 ms 5.8 MB 性能最优，不使用额外字符串
字符串版本 C++ 0 ms 6.1 MB 代码简洁，易于理解
数学版本 C# 20 ms 26.5 MB 逻辑清晰，避免字符串操作
字符串版本 Python 32 ms 16.8 MB 实现最简单

代码亮点

  1. 🎯 数学规律发现：通过分析数字序列的规律，避免暴力遍历
  2. 💡 三步解题法：系统性地分解复杂问题为简单步骤
  3. 🔍 整数溢出防护：使用long long防止中间计算溢出
  4. 🎨 多种实现方式：提供字符串和纯数学两种实现供选择

常见错误分析

  1. 🚫 整数溢出：count和start可能超出int范围，需要使用long long
  2. 🚫 索引计算错误：数字索引和位索引容易混淆，需要仔细推导
  3. 🚫 边界条件遗漏：没有正确处理n=1或小数字的情况
  4. 🚫 位数计算错误：对digits-1-digitIndex的理解有误

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
数学直接计算 O(log n) O(1) 效率最高，不需要额外空间 实现复杂，容易出错
字符串转换 O(log n) O(log n) 代码简洁，易于理解 需要额外字符串空间
暴力枚举 O(n) O(1) 思路直观 时间复杂度过高，会超时
预计算表 O(1) O(log maxN) 查询速度快 预处理复杂，空间消耗大

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第400题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！