LeetCode-Alg-400-Nth-Digit

LeetCode-Alg-400-Nth-Digit

Posted by Jae on June 18, 2019

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.

2、思路

对于这题要找第i位数是多少,我们按照位数列举部分情况找找规律:

1 2 3 4 5 6 7 8 9 总共 9*1位
10 11 ...      99 总共 90*2位
100 101 ...   999 总共 900*3位
... 所以我们只需要找到n会落在那个区间就能找到第```n```位对应的数字, 对于第一行范围为```[1, 9]```,第二行范围```[10, 189](90*2+9*1)```,第三行范围```[190, 2889](900*3+90*2+9*1)```...

假设n=12n落在了第二行,计算n与该行首元素10的差值diff2,第二行全是两位数,使用diff/2得到在首数10基础上需要跳过几个数,当找到具体某一个数后再通过diff%2就能知道是该数的第几个数字

3、实现

public class Solution {
    public int findNthDigit(int n) {
        int left = 0;
        int right = left;
        for (int i = 0; ; i++){
            left = right + 1;
            right += Math.pow(10, i) * 9 * (i + 1);
            if (n >= left && n <= right){
                // 位数是i+1
                int head = (int)Math.pow(10, i);
                // 差值
                int diff = n - left;
                // 已经找到
                int target = head + diff / (i + 1);
                // 取特定的一位
                return String.valueOf(target).charAt(diff % (i + 1)) - '0';
            }
        }
    }
}