Medium

题目描述

给你一个整数 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³¹ - 1

解题思路

这道题需要找到无限整数序列中第 n 位数字。我们需要分析数字的规律：

数字位数分布规律：

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

解题步骤：

  1. 确定位数：先判断第n位数字属于几位数
  2. 确定具体数字：在确定的位数范围内，找到具体是哪个数字
  3. 确定位置：在找到的数字中，确定是第几位

算法流程：

  • 从1位数开始，累计每种位数的总位数
  • 当累计位数>= n时，说明第n位在当前位数范围内
  • 计算出具体的数字和在该数字中的位置
  • 返回对应位置的数字

时间复杂度为O(log n)，因为位数最多约为log₁₀(n)。

代码实现

class Solution {
public:
    int findNthDigit(int n) {
        long digits = 1;
        long count = 9;
        long start = 1;
        
        // 确定n在几位数中
        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            start *= 10;
        }
        
        // 确定具体的数字
        long number = start + (n - 1) / digits;
        
        // 确定在该数字中的位置
        int index = (n - 1) % digits;
        
        // 转换为字符串并返回对应位置的数字
        string s = to_string(number);
        return s[index] - '0';
    }
};

class Solution:
    def findNthDigit(self, n: int) -> int:
        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
        
        # 确定在该数字中的位置
        index = (n - 1) % digits
        
        # 返回对应位置的数字
        return int(str(number)[index])

public class Solution {
    public int FindNthDigit(int n) {
        long 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 index = (int)((n - 1) % digits);
        
        // 返回对应位置的数字
        return number.ToString()[index] - '0';
    }
}

var findNthDigit = function(n) {
    let digits = 1;
    let count = 9;
    let start = 1;
    
    // 确定n在几位数中
    while (n > digits * count) {
        n -= digits * count;
        digits++;
        count *= 10;
        start *= 10;
    }
    
    // 确定具体的数字
    let number = start + Math.floor((n - 1) / digits);
    
    // 确定在该数字中的位置
    let index = (n - 1) % digits;
    
    // 返回对应位置的数字
    return parseInt(number.toString()[index]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)需要遍历的位数最多为log₁₀(n)级别
空间复杂度O(log n)需要将数字转换为字符串，长度为O(log n)