400.md

Question:

Find the n-th 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 < 2^31).

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.

Analysis

1-9 一共9个字符 10-99 一共90个 100-999一共900个 。。。 这个是规律

注意，边界条件很重要

Tips

Code

func findNthDigit(n int) int {
        if n < 10 {
                return n
        }
        digits := 1 // 几位数，如1，10，100，1000
        start := 1  // 起始数，1, 10, 100, 1000
        width := 9  // 该位数有多少个数，9，90，900，9000
        sum := 0
        for {
                if n < sum+digits*width {
                        targetNumber := (n-sum+1)/digits + start - 1 // 目标数
                        targetIndex := (n-sum-1)%digits + 1          // 是目标数的左数第几位，1开始
                        for i := 1; ; i++ {
                                left := targetNumber % 10
                                if i == digits-targetIndex+1 {
                                        return left
                                }
                                targetNumber /= 10
                        }
                }
                sum += digits * width
                digits++
                start *= 10
                width *= 10
        }

        return -1
}