LeetCode-剑指44-数字序列中某一位的数字

1、找规律

我们通过找规律可以发现，当位数为$x$时，其占用的位数为$x\times 9\times 10^{x-1}$。因此我们可以不断循环并增大位数$x$直至$n-x<x\times 9\times 10^{x-1}$，此时数字落在剩余的位数中。为了方便起见，我们去除0的情况即$index=n-1$。我们首先获得当前位数对应数字的起始值，即$start=(int)pow(10,d-1)$。而后我们计算我们对应的数字为$num=start+index/d$。我们确定我们需要的数字在当前数字中的第$index\%d$位。最终我们获得数字为$digit=(num/(int)(pow(10,d-digitIndex-1)))\%10$。

class Solution {
public:
    int findNthDigit(int n) {
        int d = 1, count = 9;
        while (n > (long) d * count) {
            n -= d * count;
            d++;
            count *= 10;      
        }
        int index = n - 1;
        int start = (int) pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int) (pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、二分查找

具体思路同上，区别在于我们可以通过范围确定位数不超过9，从而使用二分查找来直接进行查询。

class Solution {
public:
    int findNthDigit(int n) {
        int low = 1, high = 9;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (totalDigits(mid) < n) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int d = low;
        int prevDigits = totalDigits(d - 1);
        int index = n - prevDigits - 1;
        int start = (int) pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int) (pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }

    int totalDigits(int length) {
        int digits = 0;
        int curLength = 1, curCount = 9;
        while (curLength <= length) {
            digits += curLength * curCount;
            curLength++;
            curCount *= 10;
        }
        return digits;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33