400. 第 N 位數字

在無限的整數序列 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 的一部分

解題思路

• num記錄當前的數字
• dig記錄位數，我們的數字是從一位數，二位數…這樣遞增的
• base代表當前位數擁有多少個數字，比如有9個個位數，90個二位數

因此我們只要不斷地遍歷一位數、二位數，找出我們目標位所在在數字為num
再計算出我們需要的目標位在num中的下標

代碼

class Solution {public int findNthDigit(int n) {long base=9,dig=1;int num=0;while(n>base*dig){n-=base*dig;num+=base;base*=10;dig++;}num+=(n-1)/dig+1;long idx=(n-1)%dig+1;while(dig-->idx)num/=10;return num%10;}
}