未分類

Nth Digit

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.
提示 解題應用
Math 規律觀查

Default:

1
2
3
func findNthDigit(n int) int {
}

解答思路:

這題著手的關鍵點在於要先推算出的是原本的數值才找該個數字,而不是直接推算該個數字的規律,所以只要算出是幾位數,進而推出從該位數值開始算在第幾個而找出原本的數字,最後利用餘數找出在原本的數值上為第幾個數字。

程式碼解說:

我們可以發現長度如下:

長度1 1~9 9個
長度2 10~99 90個
長度3 100~999 900個

所以如果要找到原數的數值就先找出該數為幾位數(長度),所以就將給予的n值依序減掉長度*有幾個數,然後每減掉一次就將計算的長度+1,直到n的值為負數,此時就可以得到原本數值的長度

1
2
3
4
5
6
7
8
9
10
var size int
var sizeCount int
tmp := 9
integer := 1
for n > 0 {
size++
sizeCount = size * tmp
n = n - sizeCount
tmp *= 10
}

因為n為負值,所以只要再把剛才減掉的數給加回來,此時的n值就代表某長度開始的第n個數字,再來開始找出原本的數值,因為各長度第一個數都是10的倍數,所以我們先找出該長度的第一個值,然後再將n除上長度(結果為該長度的第幾個數值),兩個值相加後-1(因為包含該長度的第一個值)就可以找出從某長度開始的第n個數值

1
2
3
4
5
n = n + sizeCount
for i := 1; i < size; i++ {
integer *= 10
}
integer = integer + n/size - 1

不過如果n除上長度(結果為該長度的第幾個數值)有餘數存在,表示是在下一個數值,因此數值要再+1,又剛好此時的餘數正好代表該數值從前頭算起的目標數字,所以我們只要不斷從後頭除以10直到該位數字後取餘數,而如果沒有餘數存在就更容易了,表示目前找的數值的最後一位,直接跟10取餘數回傳即可

1
2
3
4
5
6
7
if n%size != 0 {
integer++
for i := 1; i <= size-n%size; i++ {
integer = integer / 10
}
}
return integer % 10

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func findNthDigit(n int) int {
var size int
var sizeCount int
tmp := 9
integer := 1
for n > 0 {
size++
sizeCount = size * tmp
n = n - sizeCount
tmp *= 10
}
n = n + sizeCount
for i := 1; i < size; i++ {
integer *= 10
}
integer = integer + n/size - 1
if n%size != 0 {
integer++
for i := 1; i <= size-n%size; i++ {
integer = integer / 10
}
}
return integer % 10
}

總結:

要推算一數列依序如字串般連結的第n個數字,著手的關鍵點在於要先推算出的是原本的數值才找該個數字,而不是直接推算該個數字的規律,所以只要算出是幾位數,進而推出從該位數值開始算在第幾個而找出原本的數字,最後利用餘數找出在原本的數值上為第幾個數字。

分享到