未分類

Ugly Number II

DynamicProgramming, Go, Heap, LeetCode, Math

Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

提示 解題應用
DynamicProgramming 規律觀查

Default:

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

解答思路:

先前雖然有一篇Ugly Number，不過那個只是檢查某數是否符合Ugly Number，而這次是要找出第n個Ugly Number，一個個做檢查的話反而浪費很多時間在非Ugly Number身上，反過來想如果是一個個由小至大組出符合條件的話會快很多，所以就透過2、3、5來一路組到第n個，至於要如何使組出的順序由小排至大，也許能藉由觀查找出規律如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2      2        2*1
3      3                  3*1
4      2*2      2*2
5      5                            5*1
6      2*3      2*3       3*2
8      2*2*2    2*4
9      3*3                3*3
10     2*5      2*5                 5*2
12     2*2*3    2*6       3*4
15     3*5                3*5       5*3
16     2*2*2*2  2*8
18     2*3*3    2*9       3*6
20     2*2*5    2*10                5*4
-----------------------------------------
24              2*12(24)  3*8(24)   5*5(25)

仔細觀查的話會發現2,3,5遞增所乘上的值正好是整個Ugly Number由小至大的順序，至於要決定下一個值就是2,3,5乘上目前各別所遞增到順序，並比較誰最小來作為下一個值，此時被當作下一個值所對應到的組合，其順序就繼續向下遞增，而如果剛好有其它組合值也相同，便也一起將順序向下遞增，知道了上述的規則之後就可以很容易的找出第n個Ugly Number。

程式碼解說:

因為每次決定下一個Ugly Number的值就正好是2,3,5各別乘上目前所遞增到順序(整個Ugly Number由小至大的順序)並找出最小值，所以就需要初始化長度為n的陣列來紀錄整個Ugly Number由小至大的順序，而第1個值要初始化值1，接著才開始向後判斷並紀錄直到找出第n個Ugly Number為止，2,3,5乘上目前各別所遞增到順序，並比較誰最小(這邊帶入一個自行宣告的函數)來作為下一個值，此時對應到最小值的組合，其順序就繼續向下遞增，最後待n個Ugly Number由小至大順序都找出來，便向上回傳最後一個值也就是第n個Ugly Number作為結果

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
func nthUglyNumber(n int) int {
	var tmp2 int
	var tmp3 int
	var tmp5 int
	var index2 int
	var index3 int
	var index5 int
	ugly := make([]int, n)
	ugly[0] = 1
	for i := 1; i < n; i++ {
		tmp2 = 2 * ugly[index2]
		tmp3 = 3 * ugly[index3]
		tmp5 = 5 * ugly[index5]
		ugly[i] = min(tmp2, tmp3, tmp5)
		if ugly[i] == tmp2 {
			index2++
		}
		if ugly[i] == tmp3 {
			index3++
		}
		if ugly[i] == tmp5 {
			index5++
		}
	}
	return ugly[n-1]
}

這部分的函數就只是單純比較三個值哪個最小，並向上回傳最小的那一個值

1
2
3
4
5
6
7
8
func min(a int, b int, c int) int {
	if a <= b && a <= c {
		return a
	} else if b <= a && b <= c {
		return b
	}
	return c
}

完整程式碼:

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
29
30
31
32
33
34
func nthUglyNumber(n int) int {
	var tmp2 int
	var tmp3 int
	var tmp5 int
	var index2 int
	var index3 int
	var index5 int
	ugly := make([]int, n)
	ugly[0] = 1
	for i := 1; i < n; i++ {
		tmp2 = 2 * ugly[index2]
		tmp3 = 3 * ugly[index3]
		tmp5 = 5 * ugly[index5]
		ugly[i] = min(tmp2, tmp3, tmp5)
		if ugly[i] == tmp2 {
			index2++
		}
		if ugly[i] == tmp3 {
			index3++
		}
		if ugly[i] == tmp5 {
			index5++
		}
	}
	return ugly[n-1]
}
func min(a int, b int, c int) int {
	if a <= b && a <= c {
		return a
	} else if b <= a && b <= c {
		return b
	}
	return c
}

總結:

要找出第n個由小至大排序的Ugly Number(該數完全由2,3,5組成)，藉由觀查找出規律會發現2,3,5遞增所乘上的值正好是整個Ugly Number由小至大的順序，每次決定下一個值的方式就是2,3,5乘上目前各別所遞增到順序，並比較誰最小來作為下一個值，此時被當作下一個值所對應到的組合，其順序就繼續向下遞增，而如果剛好有其它組合值也相同，便也一起將順序向下遞增，知道了上述的規則之後就可以很容易的找出第n個Ugly Number。

分享到