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

本问题对应的 leetcode 原文链接:剑指 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

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public int findNthDigit(int n) {
        if(n == 0){
            return 0;
        }

        long bit = 1;
        int i = 1;
        long count = 9;

        while(count < n){
            n = (int)(n - count);
            bit = bit * 10;
            i++;
            count = bit * i * 9;
        }
        // 确定是在这个区间的哪个数
        long num = bit + (n - 1) / i;
        // 确定在 Num 的那个字符
        int index = (n - 1) % i + 1;
        int res = (int)(num / Math.pow(10, i - index)) % 10;

        return res;
    }
}

时间复杂度:O(logn)
额外空间复杂度:O(1)

发表回复

后才能评论