400. 第 N 位数字

解题思路

为了不产生混淆，这里把0,99,256之类原始的1位或多位数称作值，而其间的每个位上的0、1、2、…、9称作数或数字。
代码和思路都很简单：

1. 首先我们观察一下规律：

1\~9：9个值，每个值有1个数字；
10\~99：90个值，每个值有2个数字；
100\~999：900个值，每个值有3个数字；
1000\~9999：9000个值，每个值有4个数字；
10000\~99999：90000个值，每个值有5个数字；
上面每行看作一个区间，第i个区间含有9 \times 10^{i-1} \times i个数字，第一步，我们使用一个简单的循环就能确定这个数n在哪个区间（i）以及在区间内的相对位置（n_float）：

var i float64 = 1
n_float := float64(n)
for ; n_float>9*math.Pow(10,i-1)*i ;i++{
    n_float -= 9*math.Pow(10,i-1)*i
}

循环的迭代次数不会超过$2^{31}-1$的位数，即不会大于10，可以看作O(1)时间复杂度。

2. 在区间内得到结果

思路也很简单，我们知道区间内每个值的数字长度。区间起始头加上，整除数字长度得到最终的那个数落在哪个值上；然后使用n减去前面的整除商得到残差res，残差res标明了最终结果的那个数的下标，如下面的代码所示。
这里也是O(1)时间复杂度。

分数

代码

func findNthDigit(n int) int {
    var i float64 = 1
    n_float := float64(n)
    for ; n_float>9*math.Pow(10,i-1)*i ;i++{
        n_float -= 9*math.Pow(10,i-1)*i
    }
    ii := int(i)
    n = int(n_float)
    quo := (n-1)/ii
    res := n - quo*ii

    s := strconv.Itoa(quo + int(math.Pow(10,i-1)) )

    return int(s[res-1] - '0')
}