400. Nth Digit.md

400. Nth Digit

思路

计算序列1、2、3、4、5、6、7、8、9、10、11...中第n个数字(digit，注意不是数)是什么。
我们可以将这个序列分成很多类:

• 第一类：1、2、3...9共9(设为base，下同)个数, 即每个数只包含1(设为k，下同)个数字，一共有base * k = 9 个数字;
• 第二类：10、11、12...99，base = 90，k = 2;
• 第三类：100、101、102...999,base = 900，k = 3;
• ......

设所求的digit落在数target上，则我们可根据上述规律算出target具体是多少，然后再算出所求具体是target的哪一个digit。
注意：
当我们算base * k 的时候，结果可能超过int的表示范围，所以要定义成long long型。

C++

class Solution {
public:
    int findNthDigit(int n) {
        if(n < 10) return n;
        
        // 计算target
        long long base = 9, k = 1;
        while(n > base * k){
            n -= base * k;
            base *= 10;
            k++;
        }
        int target = base / 9 + (n - 1) / k;
        
        // 计算所求digit具体是target的哪一位
        while(n % k != 0) {
           target /= 10;
           n++;
        }
        return target % 10;
    }
};