微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 44. 数字序列中某一位的数字

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

题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

限制：

  • 0 <= n < 2^31

算法

(数位统计) O(logn)

首先我们知道的是，1 位数有 10 个，2 位数有 9 个，3 位数有 9 * 10 个，4 位数有 9 * 100 个

注意：从 1 开始计数；先不考虑 0，那么一位数就变成 9 个

三步操作

  1. 确定是几位数，比如是三位数
  2. 确定是几位数的第几个数，比如是三位数的第 20 个数，即 100 + 20 – 1 = 119。
  3. 确定属于那个数的第几位

时间复杂度

总的时间复杂度即三步操作的时间复杂度

  1. int 的范围 2*10^9，所以最多是 10 位数，因此第一步操作的时间是 O(1) 的
  2. 第二步除法向上取整，也是 O(1) 的
  3. 第三步求是第几位数字是 O(log_{10}n) 的 在二进制表示中取某一位可以每次右移 1 位（即除以 2），所以是 O(log_2n) 级别的， 同理在十进制中取某一位可以每次右移 1 位（即除以 10），所以是 O(log_{10}n) 级别的

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    int findNthDigit(int n) {
        // n ++ ; // 题目是从 0 开始计数，我们的思路是从 1 开始计数，相等于把 0 算到里面了，所以 n 往后移一位
        // n -- ; // 先不考虑 0，debug 之后发现 0 也满足不需要加特判

        // i 表示几位数，s 表示 i 位数有几个，base 表示第 i 位数的第一个数是谁
        long long i = 1, s = 9, base = 1;

        // 1. 确定是几位数
        while (n > i * s) {
            n -= i * s;
            i ++ ;
            s *= 10;
            base *= 10;
        }
        // 循环结束 n 存的就是第 i 位数的第几位

        // 2. 确定是 i 位数的第几个数：(n + i - 1) / i，需要向上取整，如果有余数说明是下一个数
        // number 存的就是这个数
        int number = base + (n + i - 1) / i - 1;
        // 求余数（第几位），如果 r = 0 表示是最后一位（也就是 i，几位数就是几），如果 r = 1 表示是第一位 ... 依此类推
        int r = n % i ? n % i : i;
        // 3. 取出这一位
        for (int j = 0; j < i - r; j ++ ) number /= 10;
        // 如果是 1 位数，个位就是答案，如果是多位数，经过第 3 步处理，个位也就是答案
        return number % 10;
    }
};

Java 代码

class Solution {
    public int findNthDigit(int n) {
        long i = 1, s = 9, base = 1;

        while (n > i * s) {
            n -= i * s;
            i ++ ;
            s *= 10;
            base *= 10;
        }

        long number = base + (n + i - 1) / i - 1;
        int r = (int) (n % i != 0 ? n % i : i);

        for (int j = 0; j < i - r; j ++ ) {
            number /= 10;
        }

        return (int) (number % 10);
    }
}

Python 代码

class Solution:
    def findNthDigit(self, n: int) -> int:
        i, s, base = 1, 9, 1

        while n > i * s:
            n -= i * s
            i += 1
            s *= 10
            base *= 10

        number = base + (n + i - 1) // i - 1
        r = n % i if n % i else i

        for _ in range(i - r):
            number //= 10

        return number % 10

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer