每日一题 - 剑指 Offer 44. 数字序列中某一位的数字

题目信息

时间： 2019-07-01

题目链接：Leetcode

tag： 规律

难易程度：中等

题目描述：

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

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

示例1:

输入：n = 3 输出：3

示例2:

输入：n = 11 输出：0

提示

1. 0 <= n < 2^31

解题思路

本题难点

0<n<9时，第n位对应的数字为n。n>9时，需要确定n对应的数字的位数，再确定n对应的数字，最后确定n对应数字的哪一位上。

具体思路

将 101112⋯ 中的每一位称为 数位 ，记为 n；

将 10,11,12,⋯ 称为 数字 ，记为 num ；

数字 10是一个两位数，称此数字的 位数 为 2 ，记为 digit；

每 digit 位数的起始数字（即：1,10,100,⋯），记为 start 。

数字范围位数数字数量数位数量1～919910～99290180100～99939002700…………start~enddigit9*start9* start * digit

求解步骤：

确定 n所在 数字 的 位数 ，记为 digit ；确定 n所在的 数字 ，记为 num ；确定 n是 num中的哪一数位，并返回结果。

代码

class Solution { public int findNthDigit(int n) { int digit = 1; long start =1; long count = 9; //确定所求数位的所在数字的位数 while(n > count){ n -= count; digit += 1; start *= 10; count = digit * start * 9; } // 确定所求数位所在的数字 long num = start + (n -1) / digit; //确定所求数位在 num 的哪一数位 return Long.toString(num).charAt((n-1)%digit) - '0'; } }

复杂度分析：

时间复杂度 O(logn) ： 所求数位 n 对应数字 num 的位数 digit 最大为 O(logn) ；第一步最多循环 O(logn) 次；第三步中将 num 转化为字符串使用 O(logn) 时间；因此总体为 O(logn) 。空间复杂度 O(logn) ： 将数字 num 转化为字符串 str(num) ，占用 O(log⁡n)的额外空间。