400 第 N 位数字 位数统计模拟题

发表于

「这是我参与11月更文挑战的第 30 天，活动详情查看：2021最后一次更文挑战」。

题目描述

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

Tag : 「数学」、「模拟」

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

示例 1：

1
2
3
ini复制代码输入：n = 3

输出：3

示例 2：

1
2
3
4
5
ini复制代码输入：n = 11

输出：0

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

提示：

  • 1<=n<=231−11 <= n <= 2^{31} - 11<=n<=231−1

模拟

我们知道，对于长度为 lenlenlen 的数字的范围为 [10len−1,10len−1][10^{len - 1}, 10^{len} - 1][10len−1,10len−1]（共 9∗10len−19 * 10^{len - 1}9∗10len−1 个），总长度为：

L=len∗9∗10len−1L = len * 9 * 10^{len - 1}L=len∗9∗10len−1
因此我们可以先对 nnn 进行不断试减（更新 nnn），确定下来目标数字 xxx 的长度为多少，假设为 lenlenlen。

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

根据目标值 xxx 必然满足关系式：

(x−s+1)∗len≥n(x - s + 1) * len \geq n(x−s+1)∗len≥n
进行变形可得：

x≥⌊nlen⌋−1+sx \geq \left \lfloor \frac{n}{len} \right \rfloor - 1 + sx≥⌊lenn​⌋−1+s
对 nnn 进行最后一次的试减（更新 nnn），若恰好有 n=0n = 0n=0，说明答案为 xxx 的最后一位，可由 x % 10 取得；若大于 000，说明答案是 x+1x + 1x+1 的第 nnn 位（十进制表示，从左往右数），可由 (x + 1) / (int) (Math.pow(10, len - n)) % 10 取得。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
Java复制代码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) / (int) (Math.pow(10, len - n)) % 10);
    }
}
  • 时间复杂度：O(log⁡n)O(\log{n})O(logn)
  • 空间复杂度：O(1)O(1)O(1)

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

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

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%