LC 剑指 Offer 44. 数字序列中某一位的数字

题目描述

这是 LeetCode 上的 剑指 Offer 44. 数字序列中某一位的数字 ,难度为 中等

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。在这个序列中,第 $5$ 位(从下标 $0$ 开始计数)是 $5$,第 $13$ 位是 $1$,第 $19$ 位是 $4$,等等。

请写一个函数,求任意第 $n$ 位对应的数字。

示例 1:

1
2
3
输入:n = 3

输出:3

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

输出:0

限制:

  • $0 <= n < 2^31$

模拟

我们知道,对于长度为 $len$ 的数字的范围为 $[10^{len - 1}, 10^{len} - 1]$(共 $9 \times 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)$

补充

上述讲解可能对于新手并不友好,尤其是对一些上来只做剑指 Offer 的面试向同学,下面使用更为通俗的方式进行讲解。

对于长度 len 的所有数,其最小值为 $10^{len - 1}$,最大值为 $10^{len} - 1$,每个数所能贡献的数的个数为 $len$ 个,因此对于长度为 len 的所有数,其所能贡献的数的个数为 $(10^{len} - 10^{len - 1}) \times len$。我们专门开一个函数 getCnt 来计算长度为 len 的数的个数有多少。

然后我们从 len = 1 开始,不断对 n 进行试减(len 递增),直到 getCnt(len) <= n 不再满足。

假设此时的递增到的长度为 len,可知长度为 len 的最小值 $start = 10^{len - 1}$,我们可以通过计算偏移量 $\left \lfloor \frac{n}{len} \right \rfloor$ 并将其累加到 $start$ 中去,同时对 n 进行 $\left \lfloor \frac{n}{len} \right \rfloor \times len$ 的消减。

然后根据 n 是否为 $0$ 进行分情况讨论:

  • n 为 $0$,说明答案落在 $start - 1$ 的最后一位,即 (start - 1) % 10
  • n 不为 $0$,说明答案为 start 数值中从左往右数的第 $n$ 位,可通过解法一的方式取得,也可以将其转字符串再通过下标获取。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
long getCnt(int len) {
return (long)(Math.pow(10, len) - Math.pow(10, len - 1)) * len;
}
public int findNthDigit(int n) {
int len = 1;
while (getCnt(len) <= n) {
n -= getCnt(len);
len++;
}
long start = (long)Math.pow(10, len - 1);
start += n / len;
n -= n / len * len;
if (n == 0) return (int)(start - 1) % 10;
else return String.valueOf(start).toCharArray()[n - 1] - '0';
}
}

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

最后

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

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

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

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