400. 第N个数字/面试题44. 数字序列中某一位的数字(一般)

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。

注意:
n 是正数且在32位整数范围内 ( n < 231)。

示例 1:

输入:3

输出:3

示例 2:

输入:11

输出:0

说明:第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0,它是10的一部分。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/nth-digit

思路:

找规律,n先减去个位的9个,再减去十位的90个,再减去百位900个数,保证不小于0,然后就可以确定在几位数中,还可以计算出余数,这样,计算量比暴力遍历好很多

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int findNthDigit(int n) {
//找规律,先找到数字,再找到数字中的值
int pos = 1;//位数个位1,十位2,百位3
long start = 1;//各数位开始位置1,10,100.。。
long count = 9;//数位,9,180,2700
//循环将n减去一位数,两位数,三位数,直至小于0
while(n-count>0){
n -= count;//先减去个位,再十位,百位
start *=10;//开始位置从1到10;
pos++;//最后得到的就是在几位数中
count = 9 * start * pos;
}
//确定在哪个数字,这个难考虑
long res = start+(n-1)/pos;
//确定具体数位
int subpos = (n-1)%pos;
return Long.toString(res).charAt(subpos)-'0';
}
}