LeetCode-400-Nth-Digit

Description

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

Input:
3

Output:
3

Example 2:

Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.

描述

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 中找到第 n 个数字。

注意:
n 是正数且在 32 为整形范围内 (n < 231)。

示例 1:

 输入:
3

输出:
3

示例 2:

 输入:
11

输出:
0

说明:
第 11 个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 0，它是 10 的一部分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 位数有 1 位的数有 9 个（1-9）；位数有 2 位的有 90 个（10-99）；位数有 3 位的有 900 个（100-999）；
• 我们先确定 n 对应的数应该是几位数，假设确定了 n 对应的数的位数为 t；我们再确定 n 在有 t 位的所有数中的位置 p；
• t 位数的第一个数位 x，则通过 x，p，t 可以确定题意所求；

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-09-02 07:41:16
# @Last Modified by:   何睿
# @Last Modified time: 2019-09-02 07:55:03


class Solution:
    def findNthDigit(self, n: int) -> int:

        a, b, start = self.__find_index(n)
        return str(start + a - 1)[-1] if not b else str(start + a)[b - 1]

    def __find_index(self, n: int) -> (int, int, int):

        # cnt_digit：数字占用的位数
        # cnt_zone：有 cnt_digit 个位的数的个数
        # start：有 cnt_digit 个位的数的第一个数
        cnt_digit, cnt_zone, start = 1, 9, 1
        while n > cnt_zone * cnt_digit:# cnt_zone 消耗的总位数
            n -= cnt_zone * cnt_digit
            cnt_digit += 1
            cnt_zone *= 10
            start *= 10
        a, b = divmod(n, cnt_digit)

        return a, b, start

源代码文件在 这里。·
©本文首发于 何睿的博客，欢迎转载，转载需保留 文章来源，作者信息和本声明.