题目地址:Leetcode 400. 第 N 个数字

和剑指 offer 中的:面试题 44. 数字序列中某一位的数字 相同。

# 题目描述

在无限的整数序列 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];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

n 的取值范围决定了循环的次数,也决定了时间复杂度。

# 更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

来自: LeetCode 400.第N个数字 - JavaScript | 心谭博客
作者:心谭
Star仓库:github