大家好,我是吴师兄。
直接来看今天的题目(来自于 LeetCode 上的第 400 号问题:第 N 个数):
给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
我用图片来解释一下题目描述吧。
有一堆数字组成了一个序列:
比如从左到右开始数,绿色的 1 在第 10 位,绿色的 0 在第 11 位,红色的 1 在第 14 位,红色的 2 在第 15 位。
反过来就可以这样说,第 10 位的数字是 1,第 11 位的数字是 0 ,第 14 位的数字是 1 ,第 15位的数字是 2。
而题目就是要求我们去寻找出这个序列中第 n 位对应的数字。
而通过上面的举例,我们不难发现,实际上每一位对应的数字实际上是来源于一个整体的数字的。
比如说第 10 位的数字 1 来源于数字 10 中的 1 ,第 11 位的数字 0 来源于数字 10 中的 0,第 12 位的数字 1 来源于数字 11 中的 1 ,第 13 位的数字 1 来源于数字 11 中的 1,第 14 位的数字 1 来源于数字 12 中的 1 ,第 15 位的数字 2 来源于数字 12 中的 2。
所以,要想找出序列中第 n 位对应的数字,我们的第一步应该是先去寻找出这个数字来源于哪个数字。
这个数字来源于哪个数字听上去有些别扭,那是因为其中的两个数字有不同的含义,为了方便理解,我们可以做如下的一个约定:
那么,要想找出序列中第 n 位对应的数位,我们的第一步应该是先去寻找出这个数位来源于哪个数字。
先来找规律。
99 - 10 + 1 = 90
位,即 9 * 101。999 - 100 + 1 = 900
位,即 9 * 102。你可以发现,如果我们把 0 这个数字从长度为 1 的 1 位数中剔除,可以得到如下规律:
对于长度为 k 的 k 位数,它的范围是从 1000... 到 9999... ,总共有 9 * 10k-1。
所以,为了方便计算,0 这个数字不属于长度为 1 的 1 位数中。
对于第 n 位的数位来说,它是先数完长度为 1 的 1 位数、再数完长度为 2 的 2 位数、数完长度为 3 的 3 位数等等数过来的。
由此的话,想要找出这个数位来源于哪个数字需要先去判断一下这个数字的长度是多少。
所以,我们每次可以尝试减去某个长度的那些数字,查看剩下的这个 n 会落在哪个长度上。
公式就是:n = n - 9 * 1 * 1 - 9 * 10 * 2 - 9 * 100 * 3 - 9 * 1000 * 4 ...
,直到在减的过程中发现 n 再去剪后面的数字为变成负数为止。
此时,可以计算出 n 落在了哪个长度的数字上,比如 n 落在长度为 3 的数字上,即 n 是在 100 ~ 999 这些数字中的某个数字的数位上。
接下来就来到第三步,找出当前那个数字来,可以定义为 curNum ,比如找出 n 是落在长度为 6 的的 135674 这个数字上。
对于长度为 6 的数字来说:
反过来说:
可以注意到,n 是以 6 为单位不停的在长度为 6 的 100000 这个数字上累加 1 。
由此有了等式:curNum = 100000 + ( n - 1 ) / 6
。
更一般的,假设此时落在长度为 len 的数字上。
curNum = 10^(len-1) + ( n - 1 ) / len
。
现在,我们终于找出了这个数字!
只剩下最后一步,是这个数字上的哪一位?
比如 n = 15 ,curNum = 567890。
根据上面的结论,n 是以 6 为单位不停的在长度为 6 的 100000 这个数字上累加 1 ,意味着 n 每隔 6 个数就来到下一个数字,那么将 n 对 6 取余后的数字就是它在这个数字上的顺序。
比如 ( n - 1 ) % 6 = 3,curNum = 567890,此时数位就是 7 。
比如 ( n - 1 ) % 6 = 4,curNum = 567890,此时数位就是 8 。
比如 ( n - 1 ) % 6 = 5,curNum = 567890,此时数位就是 9 。
那这个数位怎么取出来呢?
注意到:
也就是说,假设 count = (n - 1) % 6 ,那么就可以通过 ( curNum / 10len - count - 1 ) % 10 获取到结果。
由此,这道题目就解决了,总结一下:
顺着这个思路给出代码:
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public int findNthDigit(int n) {
if ( n < 10 ) return n;
// len 表示数字的长度,即位数
// 比如数字 123 长度为 3 ,即位数为 3
// 比如数字 5678 长度为 4 ,即位数为 4
int len = 1;
// weight 表示数字所在的位数的数字的权重
// 比如长度为 2 的数字的权重是 10
// 比如长度为 3 的数字的权重是 100
// 即 10^(len-1)
int weight = 1;
// 1、先找出 n 是落在长度为多少的数字上
// 公式就是:n = n - 9 * 1 * 1 - 9 * 10 * 2 - 9 * 100 * 3 - 9 * 1000 * 4 ...
// 直到在减的过程中发现 n 再去剪后面的数字为变成负数为止。
// 由于 n 会很大,避免溢出,转一下类型
while( n > 9 * len * (long)weight ){
// 公式就是:n = n - 9 * 1 * 1 - 9 * 10 * 2 - 9 * 100 * 3 - 9 * 1000 * 4 ...
n = n - 9 * len * weight ;
// 数字的位数在不断增加
len += 1;
// 数字的权重也在不断增加
weight *= 10;
}
// 2、再找出 n 落在哪个数字上
int curNum = weight + (n - 1 ) / len ;
// 3、再找出 n 落在这个数字的第几位
int count = (n - 1) % len;
// 4、最后计算出这个数位来
return (curNum / (int) Math.pow(10,len - count - 1 )) % 10;
}
}
提交,过了!击败 100% !
今天的题目还是有点难度的,但耐心看完还是可以掌握的。