【leetcode】400 Nth Digit

发表于 | 分类于 ，

无限长数的第 n 位


描述

有数列 1 , 2 , 3 , … ,给定一个正整数 n 返回这个数的第 n 位

样例

样例1

1
2
输入: 3
输出: 3

样例2

1
2
输入: 11
输出: 0 (注意第十一位是 10 的个位)

思路

最开始想枚举 2 ^ 31 发现循环时间太长了。 后发现数字是按照 9 * 10 ^ iter * (iter+1)增长的。于是可以将一个位数缩小到一个范围，能解决小数据问题，题目直接给了一个数据
1000,0000 emmm, 时间还是很久，之后发现还可以继续缩小，想象这样一个场景， 你有 2 个苹果， 要放到容积为 2 的抽屉里面，抽屉有序，抽屉里面的空间也有序，放在哪一个位置呢 ？ 2 / 2 = 1 要放到第一个抽屉，2 % 2 = 0，放在这个抽屉的最后一个位置，可以想象一下一个二维数组的排列，求余为 0 就是最后一个数据啦！😄，所以 3 个苹果就是放在第一个抽屉的末尾再加上一个位置，也就是第二个抽屉的第一个。这也就是代码后半部分做的工作。

放一张想不清楚分苹果的人的结果图

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findNthDigit(int n) {
        string num="";
        int iter = 0;
        int endn = 0;
        int value = 0;
        while (n >  9 * pow(10, iter)*(iter + 1)) {
            endn += 9 * pow(10, iter) ;
            n -= 9 * pow(10, iter)*(iter + 1);
            iter++;
        }
        iter++; //代表检测到在iter位数的位置

        int gap = n / iter;
        int mod = n % iter;
        int start = endn + gap;
        num = to_string(start%10)+to_string(start+1);

        return num[mod] - '0';
    }
};

参考

原题链接