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

[songyy5517]

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

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

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

分析 这道题考察的是对字符序列的查找。其中字符序列的规律是它是一个从0开始的数字升序序列。因此，我们需要找到序号与数字序列之间的关系。我们可以很直接的想到：不同的数位下的数字，序号计算的方法也不同。比如，一位数的情况下，数字和序号是相等的；两位数的情况下，数字增加1，序号会对应增加2。因此，我们可以首先确定序号对应数字是几位数。然后，在该区间内确定具体是哪个数字。最后，确定数字中的具体位置。

[songyy5517]

思路：依次确定所在区间，数字以及在数字中的位置

1. 特殊值处理；

2. 单独处理个位数的情况；

3. 定义变量: 数位digit，数位包含的数字个数total_num，数位总数digit_sum；

   • 整数的数据类型使用long，防止溢出；

4. 自底向上，确定n所在的区间，即n是几位数：

   • 不断比较序号与数位区间内的数位总数，若大于某数位区间内的数位总数；

5. 确定n所在的数字：对剩下序号值除数位digit取整；

6. 确定n在数字中所在的位置：通过对剩下序号值取整取数位digit的余。

   • 定位：将数字转换为字符串，再从字符串中取出相应位置的字符，最后转换成int，返回。

复杂度分析：

• 时间复杂度： $O(log_{10}N)$ ， $N$ 为数位的数量，考虑数位总数digitsum，每次都需要乘10与 $N$ 进行比较，一共需要 $\log{10} N$ 次循环；
• 空间复杂度： $O(1)$ ，额外定义了常数级别的变量。

[songyy5517]

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int findNthDigit (int n) {
        // write code here
        // 思路：逐步细化搜索范围。
        // 1. 异常处理
        if (n < 10)
            return n;

        // 2. 定义相关变量
        long digit = 1;    // 位数
        long total_num = 9;    // 位数的数字总数
        long total_digit = 9;    // 位数的数位总数

        // 3. 确定是几位数
        while (n > total_digit){
            n -= total_digit;
            digit ++;
            total_num *= 10;
            total_digit = total_num * digit;
        }

        // 4. 确定对应的数字
        long num = (long) Math.pow(10, digit - 1) + (n - 1) / digit;

        // 5. 确定数字的具体位置
        return (num + "").charAt((int)(n % digit - 1)) - '0';
    }
}

[songyy5517]

2023/2/21 2024/3/19