【leetcode】400. Nth Digit（Python & C++）

400.1 题目描述：

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.

400.2 解题思路：

思路一：分三步走，

举个例子，比如n=23456，在9+90*2+900*3和9+90*2+900*3+9000*4之间，所以说明，这个数在1000-9999之间，是一个四位数。

一位数时，9*1=9个
二位数时，90*2=180个，
三位数时，900*3=2700个，
。。。。

以此类推，

所以设置long型变量，base代表每位数的个数，9,90,900。。。，ith代表每位数开始的那个数，1,10,100。。。，digit代表几位数，1,2,3。。。这样，循环时，判断n与base*digit的大小，进入n、base、ith、digit的调整。

23456-9-90*2-900*3=20567，

也就是，从1000开始，数20567位，那到底是落在哪个数字上呢？

1000+(20567-1)/4=6141，

所以说，在6141的某一位上，就是第n=23456位数，那到底是哪一位呢？

(20567-1)%4=2，

这说明，在6141的第3位上，也就是4。

注意的是，这里最后计算是哪个数、哪一位时，要减去1，这是因为整除代表某个数的最后一位，所以需要减1。

400.3 C++代码：

1、思路一代码（3ms）：

class Solution119 {
public:
    int findNthDigit(int n) {
        long digit = 1;//确定是哪一位
        long base = 9;//每位的数的个数
        long ith = 1;//起始值
        while (n>base*digit)
        {
            n = n - base*digit;
            digit++;
            ith = ith + base;
            base = base * 10;
        }
        return to_string(ith + (n - 1) / digit)[(n - 1) % digit] - '0';
    }
};

400.4 Python代码：

1、思路一代码（52ms）

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        digit=1
        base=9
        ith=1
        while n>base*digit:
            n=n-base*digit
            digit=digit+1
            ith=ith+base
            base=base*10
        return ord(str(ith+(n-1)/digit)[(n-1)%digit])-ord('0')