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

概述

https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

https://leetcode.com/problems/nth-digit/

暴力法

手动构造字符串，然后查询。

O(n) 时间复杂度，O(nlogn) 空间复杂度。

1. 1~9 有 9 个，占用 9 个字符；
2. 10~99 有 90 个，占用 90 * 2 个字符；
3. 100~999 有 900 个，占用 900 * 3 个字符；

我们根据 n，先求出其是几位数，然后求出其是第几个几位数的第几个即可。

下面的这个实现很脏，实现的时候注意 s * 10 这里可能会溢出，因为 n 的取值范围是 int：

class Solution {
public:
    int findNthDigit(int n) {
        if (n <= 9) return n;
        int d = 1;
        long s = 9;
        int count = 9;
        int start = 0;
        while (true) {
            start += s;
            if (n <= count + (s * 10 * (d + 1))) break;
            count += s * 10 * (d + 1);
            s *= 10;
            d ++;
        }
        n -= count;
        start ++;
        d ++;
        n --;
        int num = start + n / d;
        string numStr = to_string(num);
        return numStr[n % d] - '0';
    }
};

Links: sword-offer-44

未经允许，禁止转载，本文源站链接：https://iamazing.cn/