未分類

Nth Digit

Go, LeetCode, Math

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個數字，著手的關鍵點在於要先推算出的是原本的數值才找該個數字，而不是直接推算該個數字的規律，所以只要算出是幾位數，進而推出從該位數值開始算在第幾個而找出原本的數字，最後利用餘數找出在原本的數值上為第幾個數字。

分享到