LeetCode400. Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

1
2
3
4
5
Input:
3

Output:
3

Example 2:

1
2
3
4
5
6
7
8
Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

思路

  1. 计算n是几位数-记为digit

    • 这里比较复杂。方法是从n里面减去[1,9]9个,[10,99]90*2个,[100,999]900*3个……这些区间所占数字总个数,得到的n是剩下的在digit位数中,所用掉的数字总数。

    • 这些区间的基底是9,然后每次base都乘以10,再乘以digit位数,就得到前面范围的总数字数。可以把base*digit看作是底线,多出来的在digit进位后计算。

    • 注意这里base要用long,否则会溢出。

1
2
3
4
5
6
while (n - base * digit > 0)
{
n -= base * digit;
base *= 10;
digit++;
}
  1. 找到n所在的数是多少-记为num

    • n=10,nth=(1)/2=0,nth+base=10,他指的数是10,index=(1)%2=1

    • n=11,nth=(2)/2=1,nth+base=11,他值的数是10,index=(2)%2=0

    • n=12,nth=(3)/2=1,nth+base=11,他指的数是11,index=(3)%2=1

    • n=13,nth=(4)/2=2,nth+base=12,他所指的数是11,index=(4)%2=0

      从两位数开始找规律,发现num的值和index有关,如果index==0时,num=nth+base-1;否则num=nth+base;

  2. 确定n在num中的位置,返回该位置的值

    • 已知了index和num就可以把num转换为string来做这道题.
    • 上一步中index==0,是上一个数的最后一位,所以让index=digit位。
    • int->string->char->int的步骤如下
      1
      2
      3
      string  a = to_string(int);
      a = char;//char可以强制转换为string,a现在还是string
      int b = stoi(a);//inline int stoi(const string&)

C++ code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int findNthDigit(int n) {
//1.计算位数
int digit=1;
long base=9;
while(n-base*digit>0)
{
n-=base*digit;
base*=10;
digit++;
}

//2.找到num
int nth=n/digit;
int index=n%digit;
int num=0;
num=pow(10,digit-1)+((index==0)?nth-1:nth);

//3.转换字符串
if(index==0)
index=digit;//很容易忘掉
string a=to_string(num);
a=a[index-1];
return stoi(a);

}
};

总结

  1. 难点是第一步,怎么求n所在的数字的位数,观察1位数,两位数,三位数后,发现前面数的总和是base*digit,并且base是以十为倍数,9为底倍增的。记下溢出的n就是在当前digit位数中数字的总量。
  2. 找规律,发现num跟nth还有index有关系,共同点是都要加pow(10,digit-1),不同点是index==0的时候,nth要减一,因为那是上一个数。
  3. 最后一步是字符串转化的问题,关键语法to_string(int),(string)char,stoi(const string&)。
  4. 细节:base要用long,遇到迭代的倍增变量最好都用long.
Thanks for Support.