400. 第 N 位数字【我亦无他唯手熟尔】

简介: 400. 第 N 位数字【我亦无他唯手熟尔】

400. 第 N 位数字

难度 中等

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

输入:n = 3

输出:3

示例 2

输入:n = 11

输出:0

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

提示

  • 1 <= n <= 231 - 1
  • n 位上的数字是按计数单位(digit)从前往后数的第 n 个数,参见 示例 2

题解

思路:
先定位到哪个数i
i为w位数
n每次-w
i每次+1
退出循环的条件是n<=0
因为最后一次n-=w是负数
i多加了1
所以循环外i=i-1
n是负数对应的含义为
0是最后一位
-1是倒数第二位
依次
最后求出结果d
class Solution {
   public int findNthDigit(int n) {
        int i=1;
        int w=1;
        while(n>0){
            if(i<Math.pow(10,w)){
                n-=w;
            }
            i++;
            if(i==Math.pow(10,w)){
                w++;
            }
        }
        i=i-1;
        int d=i%10;
        for(;n<=0;n++){
            d=i%10;
            i/=10;
        }
        return d;
    }
}



官方

方法二:直接计算
已知 x 位数共有9×10x−1个,所有 x 位数的位数之和是9×10 x−1。使用 d 和 count 分别表示当前遍历到的位数和当前位数下的所有整数的位数之和,初始时 d=1,count=9。每次将 n 减去 d d×count,然后将 d 加 1,将 count 乘以 10,直到 n≤d×count,此时的 d 是目标数字所在整数的位数,n 是所有 d 位数中从第一位到目标数字的位数。


为了方便计算目标数字,使用目标数字在所有 d 位数中的下标进行计算,下标从 0 开始计数。令

index=n−1,则 index 即为目标数字在所有 d 位数中的下标,index 的最小可能取值是 0。


得到下标index 之后,即可使用方法一的做法得到无限整数序列中的第 n 位数字。

class Solution {
    public int findNthDigit(int n) {
        int d = 1, count = 9;
        while (n > (long) d * count) {
            n -= d * count;
            d++;
            count *= 10;
        }
        int index = n - 1;
        int start = (int) Math.pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }
}

作者:LeetCode-Solution

链接:https://leetcode-cn.com/problems/nth-digit/solution/di-n-wei-shu-zi-by-leetcode-solution-mdl2/

来源:力扣(LeetCode)

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


相关文章
|
10月前
260. 只出现一次的数字 III【我亦无他唯手熟尔】
260. 只出现一次的数字 III【我亦无他唯手熟尔】
25 0
|
10月前
1446. 连续字符【我亦无他唯手熟尔】
1446. 连续字符【我亦无他唯手熟尔】
27 0
|
10月前
598. 范围求和 II【我亦无他唯手熟尔】
598. 范围求和 II【我亦无他唯手熟尔】
31 0
|
10月前
496. 下一个更大元素 I【我亦无他唯手熟尔】
496. 下一个更大元素 I【我亦无他唯手熟尔】
23 0
|
10月前
500. 键盘行【我亦无他唯手熟尔】
500. 键盘行【我亦无他唯手熟尔】
44 0
|
10月前
869. 重新排序得到 2 的幂【我亦无他唯手熟尔】
869. 重新排序得到 2 的幂【我亦无他唯手熟尔】
28 0
|
10月前
|
机器学习/深度学习 算法
1816. 截断句子【我亦无他唯手熟尔】
1816. 截断句子【我亦无他唯手熟尔】
45 0
|
10月前
|
算法
136 137 260只出现一次的数字【我亦无他唯手熟尔】
136 137 260只出现一次的数字【我亦无他唯手熟尔】
50 0
|
10月前
136. 只出现一次的数字【我亦无他唯手熟尔】
136. 只出现一次的数字【我亦无他唯手熟尔】
39 0
|
10月前
367. 有效的完全平方数【我亦无他唯手熟尔】
367. 有效的完全平方数【我亦无他唯手熟尔】
29 0

热门文章

最新文章