LeetCode 400. 第 N 位数字

Categories:

题目描述
思路分析
1. 解法一：数学找规律（推荐）
相似题目

题目描述

✅ 400. 第 N 位数字

思路分析

解法一：数学找规律（推荐）

核心思路：

将无限整数序列按位数分组：1 位数（1-9）共 9 个数贡献 9 位，2 位数（10-99）共 90 个数贡献 180 位，k 位数共 9×10^(k-1) 个数贡献 k×9×10^(k-1) 位。

第一步：逐步减去每组的总位数，确定第 n 位数字落在哪个位数区间（即 k 位数范围内）。

第二步：根据剩余偏移量，确定具体是哪个 k 位数：num = 10^(k-1) + (n-1) / k。

第三步：确定是该数字的第几位：digitIndex = (n-1) % k，从高位到低位取对应字符并转为整数。

复杂度分析：

时间复杂度：O(log n)，其中 n 为目标位数，循环次数等于位数区间数量，最多约 10 次。

空间复杂度：O(1)，只使用常数个辅助变量。

class Solution {
    public int findNthDigit(int n) {
        // 当前位数（从 1 位数开始）
        int digits = 1;
        // 当前位数区间的起始数字
        long start = 1;
        // 当前位数区间的总位数
        long count = 9;

        // 找到第 n 位所在的位数区间
        while (n > count) {
            n -= count;
            digits++;
            start *= 10;
            count = (long) digits * 9 * start;
        }

        // 确定是该区间中的第几个数（从 start 开始，0-indexed）
        long num = start + (n - 1) / digits;

        // 确定是该数字从高位起的第几位（0-indexed）
        int digitIndex = (n - 1) % digits;

        // 取出对应位的数字
        return String.valueOf(num).charAt(digitIndex) - '0';
    }
}

func findNthDigit(n int) int {
    // 当前位数（从 1 位数开始）
    digits := 1
    // 当前位数区间的起始数字
    start := 1
    // 当前位数区间的总位数
    count := 9

    // 找到第 n 位所在的位数区间
    for n > count {
        n -= count
        digits++
        start *= 10
        count = digits * 9 * start
    }

    // 确定是该区间中的第几个数（从 start 开始，0-indexed）
    num := start + (n-1)/digits

    // 确定是该数字从高位起的第几位（0-indexed）
    digitIndex := (n - 1) % digits

    // 取出对应位的数字
    return int(strconv.Itoa(num)[digitIndex] - '0')
}

相似题目

题目	难度	考察点
233. 数字 1 的个数	困难	数学 / 数位统计
172. 阶乘后的零	中等	数学 / 因子统计
263. 丑数	简单	数学 / 因子判断
204. 计数质数	中等	数学 / 埃氏筛法
440. 字典序的第K小数字	困难	数学 / 字典树
268. 丢失的数字	简单	数学 / 位运算
1295. 统计位数为偶数的数字	简单	数学 / 数位统计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/92368500