LeetCode_Digit Statistics_Medium_400. Nth Digit

1.题目

给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并返回第 n 位上的数字.

示例 1：
输入：n = 3
输出：3

示例 2：
输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 0 ,它是 10 的一部分.

提示：
1 <= n <= 2³¹ - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/nth-digit

2.思路

（1）位数统计
思路参考该 LeetCode 用户题解.
① 分析题目可知,We can divide this sequence of integers into an infinite number of intervals,where the length of each number in each interval（That is, it contains the number of digits）相等,这里设为 length.

length		区间						包含数字的个数
1			[1, 9]						9 * 1 = 9 * 10^0 * 1		
2			[10, 99]					90 * 2 = 9 * 10^1 * 2		
3			[100, 999]					900 * 3 = 9 * 10^2 * 3		
4			[1000, 9999]				9000 * 4 = 9 * 10^3 * 4		
...			...							...
k			[10^(k - 1), 10^k - 1]		9 * 10^(length - 1) * length		
...			...							...

② 根据上面的规律,I can calculate first n The length of the number to which the digit in the bit belongs length,Then calculate the first n The number to which the digit in the digit belongs（设为 num）,Finally, calculate the number on the corresponding digit,The specific analysis process can be seen in the comments in the following code.

3.代码实现（Java）

//思路1————
class Solution {
    
    public int findNthDigit(int n) {
    
    	// 设第 n The number to which the digit on the digit belongs is  num,其长度 length,其初始值为 1
        int length = 1;
        while (9 * Math.pow(10, length - 1) * length < n) {
    
            n -= 9 * Math.pow(10, length - 1) * length;
            length++;
        }
        // res 保存结果
        int res = 0;
        // num The interval is  interval = [10^(length - 1), 10^length - 1],设 start is the starting point of the interval
        long start = (long) Math.pow(10, length - 1);
        // 由于 interval The length of each number is equal,Therefore, the remaining n 除以 length 就等于 num 到 s 的偏移量
        long num = start + n / length - 1;
        // 计算 res 离 num The distance of the last digit dis
        int dis = n - length * (n / length);
        if (dis == 0) {
    
        	// dis 正好为 0,那么 res 就是 num 的最后一个数字,That is, the number in the one digit
			res = (int) (num % 10);
		} else {
    
			res = (int) ((num + 1) / Math.pow(10, length - dis) % 10);
		}
        return res;
    }
}