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

Tag: 剑指-Offer Posted on 2022-02-26 20:57:48 Edited on 2022-02-26 21:37:09 Views: 137

概述

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

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