400._Nth_Digit.md

400. Nth Digit

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/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 - 时间复杂度: O(lgn)- 空间复杂度: O(1)******

这道简单题我服， tag是math，找规律

1- 9 : 9 → 只占1位 9 
10 - 99: 90 → 两位 90 * 2
100 - 999: 900 → 三位 900 * 3
1000 - 9999: 9000 → 四位 9000 * 4

改进agave大神的解法

So we can "fast-skip" those numbers until we find the size of the number that will hold our digit. At the end of the loop, we will have:

• start: first number of size size (will be power of 10)
• n: will be the number of digits that we need to count after start

How do we get the number that will hold the digit? It will be start + (n - 1) // size (we use n - 1 because we need zero-based index). Once we have that number, we can get the [(n - 1) % size]-th digit of that number, and that will be our result.

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, size, step = 1, 1, 9
        while n > size * step:
            n -= size * step
            start, size, step = start * 10, size + 1, step * 10
        num = start + (n - 1) // size # 所要取的数字，(n - 1) % size为取该数字的第几位
        mod = 0
        for i in range(size - (n - 1) % size):
            mod = num % 10
            num /= 10
        return mod

The while loop takes O(log(n)) time because a number n will have at most O(log(n)) digits. Then the return statement takes O(log(n)) time to convert the number to string. So total time complexity is O(log(n)), with O(1) extra space for the string.