400. 第N个数字*

[MyLinChi]

问题

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。

注意:
n 是正数且在32位整数范围内 ( n < 231)。

示例 1:

输入:
3

输出:
3
示例 2:

输入:
11

输出:
0

说明:
第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/nth-digit
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

求解

根据规律找到n所在的数，然后是这个数中的第几个字符。
注：有m个数，每p个为一组，求是第几组时的正确算法是(m-1)/p；求是组中的第几个元素时的正确算法是(m-1)%p。
组号从0开始，组内编号也从0开始。

class Solution {
public:
    int findNthDigit(int n) {
        int p=9,w=1;
        for(;n>(long)p*w;){
            n -= p*w;
            p *=10;
            ++w;
        }
        int num = p/9 + (n-1)/w; //在哪一个数中
        int res = (n-1)%w;
        string str = to_string(num);
        return str[res]-'0';
    }
};