LeetCode 400. 第 N 位数字——JAVA

题目描述：

给你一个整数 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 <= 231 - 1

解法：

class Solution {
    public int findNthDigit(int n) {
        if(n < 10) return n;
        long num = (long)n;
        long sum = 0;
        long posNum = 0;
        long pos = 0;
        for (long i = 1; i < num; i++) {
            sum += i * 9 * Math.pow(10, i - 1);
            if (sum > num) {
                sum -= i * 9 * Math.pow(10, i - 1);
                posNum = i * 9 * (long) (Math.pow(10, i - 1));
                pos = i;
                break;
            }
        }
        int targerNum = -1;
        for (long i = 0; i < posNum; i++) {
            if (sum >= num) {
                long target = (long) (Math.pow(10, pos - 1))  + (i - 1);
                long offset = Math.abs(sum - pos - num);
                targerNum = Long.toString(target).charAt((int)offset - 1) - '0';
                break;
			}
            sum += pos;
        }
        return targerNum;
    }
}

思路：

1.个位数直接返回

2.1位数的总个数为1*9，

两位数的总位数为 2 * 90 (两位数占两个位,数量为90个)，

三位数总位数为3*900((三位数占三个位,数量为900个))，

四位数的总位数为3*9000((四位数占四个位,数量为9000个))，

依次类推，N位数的总位数为 N * 9 * 10 ^(N-1)

于是有了

sum += i * 9 * Math.pow(10, i - 1);

前面所有位数的总和。

于是我们需要得到一个值，那就是多少位之和大于等于(大于是因为目标值可能在某一个数的某一个位，这个位我们称之为偏移值)我们目标值

        for (long i = 1; i < num; i++) {
            sum += i * 9 * Math.pow(10, i - 1);
            if (sum > num) {
                sum -= i * 9 * Math.pow(10, i - 1);
                posNum = i * 9 * (long) (Math.pow(10, i - 1));
                pos = i;
                break;
            }
        }

这一段代码就是找到大于目标值的总位数之和，其中sum是前面位数累计和，posNum是未超过目标值的计算起始值，比如目标值在7位数和8位数和的中间，于是我们先计算出前面所有7位数之和，然后新的计算值从10^8开始，而这里得到的值就是当前需要统计的位数。

        int targerNum = -1;
        for (long i = 0; i < posNum; i++) {
            if (sum >= num) {
                long target = (long) (Math.pow(10, pos - 1))  + (i - 1);
                long offset = Math.abs(sum - pos - num);
                targerNum = Long.toString(target).charAt((int)offset - 1) - '0';
                break;
			}
            sum += pos;
        }
        return targerNum;

然后从10^N开始遍历，每次偏移量就是N次方，得到超过目标值的领界值,然后通过累计值减去目标值得到偏移量,

偏移的目标值是N次方的起始值+遍历次数

这个值转化成字符串，通过偏移量得到字符串中的字符，然后转化成数字即可

Long.toString(target).charAt((int)offset - 1) - '0';

这里charAt是从0开始，所以需要把我们计算出来的偏移量减去1