400. 第 N 位数字
难度 中等
给你一个整数 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
- 第
n位上的数字是按计数单位（digit）从前往后数的第n个数，参见 示例 2 。
题解
思路： 先定位到哪个数i i为w位数 n每次-w i每次+1 退出循环的条件是n<=0 因为最后一次n-=w是负数 i多加了1 所以循环外i=i-1 n是负数对应的含义为 0是最后一位 -1是倒数第二位 依次 最后求出结果d
class Solution { public int findNthDigit(int n) { int i=1; int w=1; while(n>0){ if(i<Math.pow(10,w)){ n-=w; } i++; if(i==Math.pow(10,w)){ w++; } } i=i-1; int d=i%10; for(;n<=0;n++){ d=i%10; i/=10; } return d; } }
官方
方法二：直接计算
已知 x 位数共有9×10x−1个，所有 x 位数的位数之和是9×10 x−1。使用 d 和 count 分别表示当前遍历到的位数和当前位数下的所有整数的位数之和，初始时 d=1，count=9。每次将 n 减去 d d×count，然后将 d 加 1，将 count 乘以 10，直到 n≤d×count，此时的 d 是目标数字所在整数的位数，n 是所有 d 位数中从第一位到目标数字的位数。
为了方便计算目标数字，使用目标数字在所有 d 位数中的下标进行计算，下标从 0 开始计数。令
index=n−1，则 index 即为目标数字在所有 d 位数中的下标，index 的最小可能取值是 0。
得到下标index 之后，即可使用方法一的做法得到无限整数序列中的第 n 位数字。
class Solution { public int findNthDigit(int n) { int d = 1, count = 9; while (n > (long) d * count) { n -= d * count; d++; count *= 10; } int index = n - 1; int start = (int) Math.pow(10, d - 1); int num = start + index / d; int digitIndex = index % d; int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10; return digit; } }
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/nth-digit/solution/di-n-wei-shu-zi-by-leetcode-solution-mdl2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
