LeetCode 400.第N个数字 - JavaScript
LeetCode 400.第N个数字 - JavaScript
心谭博客
发布于 2020-04-21 10:39:05
发布于 2020-04-21 10:39:05
题目描述
在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。
注意：n 是正数且在 32 位整形范围内 ( n < 2^31)。
这里的第 n 个数字，其实指的是第 n 位数字。例如输入 11，那么应该输出 0（来自于数字 10）。
解法：找规律
写出这些数据，可以发现：
- 1 位数字有 9 个：1-9
- 2 位数字有 90 个：10-99
- 3 位数字有 900 个：100-999
- k 位数字有
9 * 10^k个
所以解决思路就是先通过循环，确定所要查找的数字落在第几位。最后通过计算找出数字即可。例如对于 n=13 来说，过程如下：
- n 大于 9，说明不是 1 位数字，n 更新为 n - 9 = 4。继续循环。
- n 小于 90，说明是 2 位数字。
- 计算要找的数字 num：
num = 10 + int(4/2) - 1 = 11 - 计算结果在 num 中的位置：
pos = 4 - 2 * (11 - 10) - 1 = 1
代码实现如下：
// ac地址：https://leetcode-cn.com/problems/nth-digit/
// 原文地址：https://xxoo521.com/2020-03-09-n-number/
/**
* @param {number} n
* @return {number}
*/
var findNthDigit = function(n) {
for (let bit = 1; bit < 32; ++bit) {
const startNum = Math.pow(10, bit - 1);
const bitSum = 9 * startNum * bit;
if (n > bitSum) {
n -= bitSum;
} else {
let num = startNum + Math.ceil(n / bit) - 1;
let pos = n - bit * (num - startNum) - 1;
return num.toString(10)[pos];
}
}
};n 的取值范围决定了循环的次数，也决定了时间复杂度。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-03-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录