剑指OfferV2(增) -- 数字序列中某一位的数字

秦怀杂货店

发布于 2022-02-15 15:01:15

4480

Part0前言

剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/ 刷题仓库介绍：刷题仓库：CodeSolution 编程知识库：https://github.com/Damaer/Coding 文档地址：https://damaer.github.io/Coding/#/ 本题为剑指Offer V2 版本新增题目，正在补充题目以及之前题目的C++版本，欢迎关注...

Part1数字序列中某一位的数字

1题目描述

数字以 0123456789101112131415... 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。

示例1

输入：0
返回值：0

示例2

输入：2
返回值：2

示例3

输入：13
返回值：1

2思路 & 解答

这道题是数学规律题，先找到规律，下面是几个区间

1. 小于10，1~9，9个数字，9位
1. 大于等于10小于100，10~99，90个数字，180位
1. 大于等于100且小于1000，100~999，900个数字，2700位
2. ......

当我们查找第 n 位的时候，需要先计算出 n 落在哪一个区间内，比如 8 就在第一个区间内，161 就在第二个区间内，1314 就在第 3 个区间内；

计算出区间之后，需要计算出所在的数字是哪一个，比如 1314 （一共4位），然后再计算位数。

Java 代码实现如下：

public class Solution44 {
    public int findNthDigit (int n) {
        if (n <= 0) return 0;
        // 开始数值
        long start = 1;
        // 位数
        long digit = 1;
        // 个数
        long count = 9;

        while (n > count) {
            n -= count;
            start *= 10;
            digit += 1;
            count = start * 9 * digit;
        }
        // 所在的数字
        String num = (start + (n - 1) / digit) + "";
        // 计算位数（第几个数字）
        int index = (int)((n - 1) % digit);
        return Integer.parseInt(num.charAt(index) + "");
    }
}

C++ 代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int findNthDigit(int n) {
        if (n <= 0) return 0;
        // 开始数值
        long start = 1;
        // 位数
        long digit = 1;
        // 个数
        long count = 9;

        while (n > count) {
            n -= count;
            start *= 10;
            digit += 1;
            count = start * 9 * digit;
        }
        // 所在的数字
        string num = to_string(start + (n - 1) / digit) + "";
        // 计算位数（第几个数字）
        int index = (int) ((n - 1) % digit);
        return num[index] - '0';
    }
};

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-01-04，如有侵权请联系 cloudcommunity@tencent.com 删除

https