LeetCode_位数统计_中等_400.第 N 位数字

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 用户题解。
① 分析题目可知，我们可以将该整数序列分割成无数个区间，其中每个区间内每个数的长度（即包含数字的个数）相等，这里设为 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		
...			...							...

② 根据上面的规律，我可以先计算出第 n 位上的数字所属的数的长度 length，然后再计算出第 n 位上的数字所属的数（设为 num），最后再计算对应位上的数字即可，具体的分析过程可见下面代码中的注释。

3.代码实现（Java）

//思路1————
class Solution {
    
    public int findNthDigit(int n) {
    
    	// 设第 n 位上的数字所属的数为 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 所在的区间为 interval = [10^(length - 1), 10^length - 1]，设 start 为该区间的起点
        long start = (long) Math.pow(10, length - 1);
        // 由于 interval 内每个数的长度相等，故此时剩余的 n 除以 length 就等于 num 到 s 的偏移量
        long num = start + n / length - 1;
        // 计算 res 离 num 的最后一个数字的距离 dis
        int dis = n - length * (n / length);
        if (dis == 0) {
    
        	// dis 正好为 0，那么 res 就是 num 的最后一个数字，即个位上的数字
			res = (int) (num % 10);
		} else {
    
			res = (int) ((num + 1) / Math.pow(10, length - dis) % 10);
		}
        return res;
    }
}