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

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

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

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

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

当前位置: 算法 > 剑指offer > 剑指offer 44. 数字序列中某一位的数字
本文链接:https://www.mianshi.online/2759.html

题目描述

数字以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完整版