Erlo

LeetCode-400. 第N位数字

收藏 2023-01-01 19:00:09   25   博客园
页面报错/反馈
点赞

题目来源

400. 第 N 位数字

题目详情

给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

示例 1:

输入: n = 3
输出: 3

示例 2:

输入: n = 11
输出: 0
解释: 第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ,它是 10 的一部分。

提示:

  • 1 <= n <= 231 - 1

题解分析

本题的解题关键是如何定位到指定字符所在的数字。通过仔细观察序列数字串,可以发现,位数为1的数字个数为9,位数为2的数字个数为90,位数为3的数字个数为900,依次类推。

按照上述规律,可以进一步每种位数中包含的字符个数,它们是数字个数与位数的乘积。通过这种模拟法,可以首先求出所述字符是哪种位数的,进而根据除余运算可以计算出这个数字的具体指。最后,问题就转换为了求解某个具体数字的某位上的字符。

算法实现

class Solution {
    public int findNthDigit(int n) {
        // 9 * 1, 90 * 2, 900 * 3, 9000 * 4
        int bit = 1;
        long cnt = 9;
        while (bit * cnt < n) {
            n -= bit * cnt;
            bit++;
            cnt = cnt * 10; 
        }
        // rest表示在bit位数集中的第几字符位,减一是为了下标从0开始计算
        int rest = (int) (n - 1);
        // start表示bit位数集中的起始元素
        int start = (int) Math.pow(10, bit-1);
        // n是bit位数集中的第几个元素
        int pt = rest / bit;
        // num表示第n个字符所在的元素
        int num = start + pt;
        // seq表示对应元素的第几个字符(从左往右)
        int seq = rest % bit;

        // 后续问题转换为求num数字的第seq个字符是什么,1203

        // 去除第seq个字符后面数字后的结果
        int left = num / (int) Math.pow(10, bit - seq -1);
        return left % 10;
    }
}

登录查看全部

参与评论

评论留言

还没有评论留言,赶紧来抢楼吧~~

返回顶部

给这篇文章打个标签吧~

棒极了 糟糕透顶 好文章 PHP JAVA JS 小程序 Python SEO MySql 确认