400. Nth Digit 第 N 位数字

题目地址：https://leetcode.com/problems/reach-a-number/description/

题目描述

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

Note:

1、 nispositiveandwillfitwithintherangeofa32-bitsignedinteger(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.

题目大意

找出一个连续的自然数序列中，第N位数字是多少。

解题方法

我们要得到第N位数字，如果直接暴力是超时的。正确的做法是找规律：个位数字有9个，2位数字有910=90个，3位数字有9100=900个……所以我们先求出n是几位数字，然后判断第n个数字应该落在哪个自然数上，最后再求这个自然数会落在自然数的那一位上。

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        _len = 1
        cnt = 9
        start = 1
        while n > _len * cnt:
            n -= _len * cnt
            _len += 1
            cnt *= 10
            start *= 10
        start += (n - 1) / _len
        return int(str(start)[(n - 1) % _len])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

参考资料：http://www.cnblogs.com/grandyang/p/5891871.html

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发