剑指Offer Java版 面试题44：数字序列中某一位的数字

题目：数字以0123456789101112131415···的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

练习地址

https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

参考答案

class Solution {
    public int findNthDigit(int n) {
        if (n < 0) {
            return -1;
        }
        int digits = 1;
        while (true) {
            long numbers = countOfIntegers(digits);
            if (n < numbers * digits) {
                return digitAtIndex(n, digits);
            }
            n -= digits * numbers;
            digits++;
        }
    }

    private long countOfIntegers(int digits) {
        if (digits == 1) {
            return 10;
        }
        long count = (long) Math.pow(10, digits - 1);
        return 9 * count;
    }

    private int digitAtIndex(int index, int digits) {
        int number = beginNumber(digits) + index / digits;
        int indexFromRight = digits - index % digits;
        for (int i = 1; i < indexFromRight; i++) {
            number /= 10;
        }
        return number % 10;
    }

    private int beginNumber(int digits) {
        if (digits == 1) {
            return 0;
        }
        return (int) Math.pow(10, digits - 1);
    }
}

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(logn)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题