找规律

题目链接-来源：力扣（LeetCode）

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

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

示例 1：

输入：n = 3
输出：3

思路：

此题与上题一样，需要找到数字的规律，方能在O(logn)的时间复杂度内解决，避免暴力解。
我们正向思考这个问题，如果给你某个具体的数字，让你计算出这个序列中，这个数字落在第几位，应该如何计算？比如，数字 ‘10’，落在序列 “012345678910”的第 11 位（最开头数字记为第 0 位）。我们可以有以下思路，’10’ 是个「两位数」，因此其之前「一位数」的总数是确定的，（由于 ‘0’ 是第 0 个，不参与计数）有 10 - 1 = 9 个，再加上 ‘10’ 在「两位数」中排第 1 个，于是其末位就位于 2 * 1（2位数，第1个） = 2 的偏移位置，最终计算出 ‘10’ 的末位于第 11 位。
现在我们回到题解，如果我们能通过 「末位位于第 11 位」这个条件，反推出 「这个数字是 ‘10’」，进而就能够确定这个数字的末位是 ‘0’（将该数字对 10 进行求余即可）。
回顾之前的计算，我们可以已知以下数字的个数：「一位数」共有 9 个，共计 9 * 1 = 9 位，「二位数」共有 90 个，共计 90 * 2 = 180 位，…，「k 位数」共有 9 * 10^(n - 1) 个，共计 9 * 10^(k - 1) * k 位。 这样，我们对输入的 n 迭代地扣除前面这些已知的数字（9，180，…），直到 n 不足以扣除下一个数时，我们就找到了 n 是「几位数」，这个 「几位数」是 10 的某次幂，记为 start。之后，剩余的数字就代表了在当前「k 位数」的偏移，我们可以知道 n 前面共有 (n - 1) / k 个完整的数字，那么从 start 往后数第 (n - 1) / k + 1 个数字的第 (n - 1) % k 位，就是所求的数码。
时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findNthDigit(int n) {
        if (n == 0) {
            return 0;
        }
        int digit = 1;
        long start = 1, count = digit * start * 9;
        while (n > count) {
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }
        
        long num = (n - 1) / digit + start;
        int index = (n - 1) % digit;
        
        return Long.toString(num).charAt(index) - '0';
    }
}