跳至主要內容

0400. 第 N 位数字

ITCharge大约 4 分钟

0400. 第 N 位数字open in new window

  • 标签:数学、二分查找
  • 难度:中等

题目链接

题目大意

描述:给你一个整数 nn

要求:在无限的整数序列 [1,2,3,4,5,6,7,8,9,10,11,...][1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 nn 位上的数字。

说明

  • 1n23111 \le n \le 2^{31} - 1

示例

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

解题思路

思路 1:找规律

数字以 01234567891011121314150123456789101112131415… 的格式序列化到一个字符序列中。在这个序列中,第 55 位(从下标 00 开始计数)是 55,第 1313 位是 11,第 1919 位是 44,等等。

根据题意中的字符串,找数学规律:

  • 11 位数字有 99 个,共 99 位:123456789123456789
  • 22 位数字有 9090 个,共 2×902 \times 90 位:10111213...989910111213...9899
  • 33 位数字有 900900 个,共 3×9003 \times 900 位:100...999100...999
  • 44 位数字有 90009000 个,共 4×90004 \times 9000 位: 1000...99991000...9999
  • ……

则我们可以按照以下步骤解决这道题:

  1. 我们可以先找到第 nn 位所在整数 numbernumber 所对应的位数 digitdigit
  2. 同时找到该位数 digitdigit 的起始整数 startstart
  3. 再计算出 nn 所在整数 numbernumbernumbernumber 等于从起始数字 startstart 开始的第 n1digit\lfloor \frac{n - 1}{digit} \rfloor 个数字。即 number = start + (n - 1) // digit
  4. 然后确定 nn 对应的是数字 numbernumber 中的哪一位。即 digitidx=(n1)moddigitdigit\underline{}idx = (n - 1) \mod digit
  5. 最后返回结果。

思路 1:代码

class Solution:
    def findNthDigit(self, n: int) -> int:
        digit = 1
        start = 1
        base = 9
        while n > base:
            n -= base
            digit += 1
            start *= 10
            base = start * digit * 9

        number = start + (n - 1) // digit
        digit_idx = (n - 1) % digit
        return int(str(number)[digit_idx])

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n)
  • 空间复杂度O(1)O(1)

思路 2:二分查找

假设第 nn 位数字所在的整数是 digitdigit 位数,我们可以定义一个方法 totalDigits(x)totalDigits(x) 用于计算所有位数不超过 xx 的整数的所有位数和。

根据题意我们可知,所有位数不超过 digit1digit - 1 的整数的所有位数和一定小于 nn,并且所有不超过 digitdigit 的整数的所有位数和一定大于等于 nn

因为所有位数不超过 xx 的整数的所有位数和 totalDigits(x)totalDigits(x) 是关于 xx 单调递增的,所以我们可以使用二分查找的方式,确定第 nn 位数字所在的整数的位数 digitdigit

nn 的最大值为 23112^{31} - 1,约为 2×1092 \times 10^9。而 99 位数字有 9×1089 \times 10^8 个,共 9×9×108=8.1×109>2×1099 \times 9 \times 10^8 = 8.1 \times 10^9 > 2 \times 10 ^ 9,所以第 nn 位所在整数的位数 digitdigit 最多为 99 位,最小为 11 位。即 digitdigit 的取值范围为 [1,9][1, 9]

我们使用二分查找算法得到 digitdigit 之后,还可以计算出不超过 digit1digit - 1 的整数的所有位数和 predigits=totalDigits(digit1)pre\underline{}digits = totalDigits(digit - 1),则第 nn 位数字所在整数在所有 digitdigit 位数中的下标是 idx=npredigits1idx = n - pre\underline{}digits - 1

得到下标 idxidx 后,可以计算出 nn 所在整数 numbernumbernumbernumber 等于从起始数字 10digit110^{digit - 1} 开始的第 idxdigit\lfloor \frac{idx}{digit} \rfloor 个数字。即 number = 10 ** (digit - 1) + idx // digit

该整数 numbernumber 中第 idxmoddigitidx \mod digit 即为第 nn 位上的数字,将其作为答案返回即可。

思路 2:代码

class Solution:
    def totalDigits(self, x):
        digits = 0
        digit, cnt = 1, 9
        while digit <= x:
            digits += digit * cnt
            digit += 1
            cnt *= 10
        return digits

    def findNthDigit(self, n: int) -> int:
        left, right = 1, 9
        while left < right:
            mid = left + (right - left) // 2
            if self.totalDigits(mid) < n:
                left = mid + 1
            else:
                right = mid

        digit = left
        pre_digits = self.totalDigits(digit - 1)
        idx = n - pre_digits - 1
        number = 10 ** (digit - 1) + idx // digit
        digit_idx = idx % digit
    
        return int(str(number)[digit_idx])

思路 2:复杂度分析

  • 时间复杂度logn×loglogn\log n \times \log \log n,位数上限 DDlogn\log n,二分查找的时间复杂度为 logD\log D,每次执行的时间复杂度为 DD,总的时间复杂度为 D×logD=O(logn×loglogn)D \times \log D = O(\log n \times \log \log n)
  • 空间复杂度O(1)O(1)

参考资料