力扣400——第 N 位数字（模拟，数学）

66 阅读 0 评论 44 点赞

我是靠谱客的博主昏睡网络，最近开发中收集的这篇文章主要介绍力扣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 ，它是 10 的一部分。

提示：
1 <= n <= 231 - 1

思路

模拟，先找位数，再找哪个数，再找第几位
首先找规律
一位数：1到9 共9个数字
二位数：10到99 共9*10 = 90个数字（10包括数字1，0；11包括数字1，1）
三位数：100到999 共9*10*10 = 900个数字
对于d位数，总数字个数为 $9*10^{(d-1)}$

模拟步骤
1、对于给定的n，先找到其所在的位数，通过循环递减，位数和个数递增，确定n所在的数字的位数
2、对于确定位数，先找到起始的那个数，即10、100、1000这样的 $10^{d-1}$ 数
3、确定n所在的数，因为要考虑下标0(除法运算，取模运算都是从0开始)，所以先对n做减1处理，通过d位数的起始数+此刻的n包含多少完整d位数，就是对应的数字，将其转字符串
4、n对位数取模，对于该字符串，现在的第余数位就是答案

举例来看：

n=3，首先找到属于1位数；之后确定1位数起始数字为1；此时n=3包含3个一位数（包括起始数字），所以从起始数字加2即可得到3对应的数字，所以在前面要对n减一处理，计算机语言都是0开头，将其转字符串"3";n对1取模得0，所以第0位就是答案

n=11，首先找到属于2位数，此时n = 11 - 9 = 2；因为考虑下标0，对n减一处理，此时n = 1；二位数起始数字10，当前n不能包含完整二位数（n/2=0），所以对应数字为10，将其转字符串"10"；n对2取模，得到当前n应在对应数字的下标n%2位，即下标1位，"10"下标1为0，得到答案。

n=15，首先找到属于2位数，此时n = 6；减一处理，n = 5；二位数起始数字10，当前你包含n/2 = 2个完整两位数，所以n对应数字为10+n/2 = 12，转字符串"12"；n在对应数字还剩余n%2=1位，所以"12"的下标1对应数字2即为答案。

代码

class Solution {
public:
    int findNthDigit(int n) {
        int d = 1,count = 9;
        while(n > (long)d*count) {
            n -= d*count;
            d++;
            count *= 10;
        }
        n--;
        int begin = (int)pow(10,d-1);
        int num = begin + n/d;
        string s = to_string(num);
        return s[n%d] - '0';    
    }
};