LC 400. 第 N 位数字

题目描述

这是 LeetCode 上的 400. 第 N 位数字 ,难度为 中等

给你一个整数 $n$ ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 $n$ 位数字。

示例 1:

1
2
3
输入:n = 3

输出:3

示例 2:
1
2
3
4
5
输入:n = 11

输出:0

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

提示:

  • $1 <= n <= 2^{31} - 1$

模拟

我们知道,对于长度为 $len$ 的数字的范围为 $[10^{len - 1}, 10^{len} - 1]$(共 $9 * 10^{len - 1}$ 个),总长度为:

因此我们可以先对 $n$ 进行不断试减(更新 $n$),确定下来目标数字 $x$ 的长度为多少,假设为 $len$。

然后直接计算出长度 $len$ 的最小值为 $s = 10^{len - 1}$,由于范围内的数长度都是 $len$,因此我们可以直接定位到目标数字 $x$ 为何值。

根据目标值 $x$ 必然满足关系式:

变形可得:

对 $n$ 进行最后一次的试减(更新 $n$),若恰好有 $n = 0$,说明答案为 $x$ 的最后一位,可由 x % 10 取得;若大于 $0$,说明答案是 $x + 1$ 的第 $n$ 位(十进制表示,从左往右数),可由 (x + 1) / (int) (Math.pow(10, len - n)) % 10 取得。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int findNthDigit(int n) {
int len = 1;
while (len * 9 * Math.pow(10, len - 1) < n) {
n -= len * 9 * Math.pow(10, len - 1);
len++;
}
long s = (long) Math.pow(10, len - 1);
long x = n / len - 1 + s;
n -= (x - s + 1) * len;
return n == 0 ? (int) (x % 10) : (int) ((x + 1) / Math.pow(10, len - n) % 10);
}
}

  • 时间复杂度:$O(\log{n})$
  • 空间复杂度:$O(1)$

补充

看到评论区,不少小伙伴对上述推导理解感到困难。我们可以换个思路,从更加纯粹直接的角度进行分析。

首先和上述解法一样,我们还是需要先对 $n$ 进行第一阶段的试减(更新 $n$),得到目标数字所在的数值的长度 $len$ 是多少。

然后根据 $len$ 我们可以算得起点值 $s = 10^{len - 1}$(例如 $len = 2$ 时,$s = 10$;$len = 3$ 时,$s = 100$)。

由于每个数长度都是 $len$,因此我们可以用剩余的数 $n$ 除 $len$,得到从起点的偏移量是多少(并将偏移量累加更新到 $s$),然后对 $n$ 做第二阶段的试减,减去的值就是 $\left \lfloor \frac{n}{len} \right \rfloor * len$。

如果试减后结果恰好为 $0$,那么答案为当前 $s$ 的最后一个数字;否则(试减结果大于 $0$),则是 $x + 1$ 中(十进制表示,从左往右数)的第 $n$ 个数字。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int findNthDigit(int n) {
int len = 1;
while (len * 9 * Math.pow(10, len - 1) < n) {
n -= len * 9 * Math.pow(10, len - 1);
len++;
}
long s = (long) Math.pow(10, len - 1);
s += n / len - 1;
n -= len * (n / len);
return n == 0 ? (int) (s % 10) : (int) ((s + 1) / Math.pow(10, len - n) % 10);
}
}

  • 时间复杂度:$O(\log{n})$
  • 空间复杂度:$O(1)$

最终你会发现,两种做法是完全等价的,只是对应了不同的角度描述而已。


最后

这是我们「刷穿 LeetCode」系列文章的第 No.400 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!