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)时间复杂度。

分数

file

代码

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')
}

类似文章

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注