Nth Digit

发表于 | 分类于

Nth Digit

题目描述：

给定一个数字n，要求找到从1,2,3,4,….排列中的第n位数字。

例子：

具体描述见LeetCode400

解题思路：

首先我们用digit变量来寻找到这一位数字所在数的位数是多少。通过循环不断的进行n的减少直到n可能小于0；此时我们就知道了这位数的位数；根据剩下的n来找到对应的数字；最后找到对应位数上的数字即可。详细解法可以见discuss

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findNthDigit(int n) {
        long base = 9;
        int digits = 1;
        while(n - digits * base > 0){
            n -= base * digits;
            base = base * 10;
            digits++;
        }//此时已经得到了位数
        int index = n % digits;
        if (index == 0)
            index = digits;
        long num = 1;
        for (int i = 1; i < digits; i++)
            num *= 10;
        num += (index == digits) ? n / digits - 1 : n / digits;
        //找到对应的数字
        for (int i = index; i < digits; i++)
            num /= 10;
        return num % 10;
        //找到对应位数的数字
    }
};