剑指offer44之数字序列中某一位的数字

剑指offer44之数字序列中某一位的数字

数字序列中某一位的数字

• 前言
• 一、例题
• • 1、题目
  • 2、示例
• 二、题解
• • 1、找规律
  • 2、示例
  • 3、Code
• 总结
• 参考文献

前言

找到问题中的规律，根据规律来完成代码。

一、例题 1、题目

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

2、示例

示例 1：
输入：n = 3
输出：3

示例 2：
输入：n = 11
输出：0

二、题解 1、找规律 范围数多少个数几位数（bitCount）共占多少位（多少个数 x 几位数）1~9919 x 1 = 910~9999 - 10 + 1 = 90290 x 2 = 180100~999999 - 100 + 1 = 9003900 x 3 = 2700 2、示例

第200个数，
=> 200 = 9 + 180 + 11，
=> bitCount = 3，surplus = 11，
=> data = 100 + (11 - 1) / 3 = 103，index = (11 - 1) % 3 = 1
=> result = "103".charAt(1) - '0' = '0' - '0' = 0;

3、Code

public int findNthDigit(int n) {
        
        int surplus = n;

        int bitCount = 1;
        long base = 1;
        long count = 9;

        while (surplus > count) {
            surplus -= count;
            base *= 10;
            bitCount++;
            count = bitCount * 9 * base;
        }
        long data = base + (surplus - 1) / bitCount;
        int index = (surplus - 1) % bitCount;
        return Long.toString(data).charAt(index) - '0';
    }

总结

1）细心找到其中的规律，该题的规律就是如何定位？

参考文献

[1] LeetCode 原题
[2] LeetCode用户评论