0400._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

参考微信大佬caitao7的代码，加了注释，修改了变量名

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        digits_count = 1 # 当前区间数字的位数
        while n >= 9 * 10 ** (digits_count-1) * digits_count:
            n -= 9 * 10 ** (digits_count-1) * digits_count
            digits_count += 1
        target_num = 10 ** (digits_count-1) - 1 + n // digits_count # 我们要从这个数字上面取digit
        target_digit = n % digits_count # 我们要从这个数字上面取第几位digit
        if target_digit == 0: # 取第0位digit其实就是说这个数字的个数位刚好到达我们的第n位digit
            return target_num % 10
        return ((target_num+1) / 10 ** (digits_count-target_digit)) % 10

思路 2 - 时间复杂度: O(lgn)- 空间复杂度: O(1)******

改进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.