未分類

Super Ugly Number

Go, Heap, LeetCode, Math

Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:

  1. 1 is a super ugly number for any given primes.
  2. The given numbers in primes are in ascending order.
  3. 0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000.
  4. The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Default:

1
2
3
func nthSuperUglyNumber(n int, primes []int) int {
}

解答思路:

建議可以先參考先前Ugly Number II的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做修改而已，如果能找出第n個Ugly Number(由2,3,5組成)，那麼一樣要找出第n個Ugly Number(由給予的數所組成)就不會太困難。

要找出第n個由小至大排序的Ugly Number(該數完全由給予的數所組成)，每次決定下一個值的方式就是由Ugly Number的組成數乘上目前各別所遞增到順序，並比較誰最小來作為下一個值，此時被當作下一個值所對應到的組合，其順序就繼續向下遞增，而如果剛好有其它組合值也相同便也一起將順序向下遞增。

程式碼解說:

其實應該不需要多做什麼解釋，與先前相比Ugly Number從原本由2,3,5組成變成題目指定，因此就都只是將綁定的三個變數處理改為由指定組合所對應到的相同長度陣列來儲存並用迴圈處理而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func nthSuperUglyNumber(n int, primes []int) int {
	ugly := make([]int, n)
	tmp := make([]int, len(primes))
	count := make([]int, len(primes))
	ugly[0] = 1
	for i := 1; i < n; i++ {
		for j, prime := range primes {
			tmp[j] = prime * ugly[count[j]]
		}
		ugly[i] = min(tmp)
		for k, v := range tmp {
			if v == ugly[i] {
				count[k]++
			}
		}
	}
	return ugly[n-1]
}

這部分的函數就只是單純比較陣列中哪個元素最小，並向上回傳最小的那一個元素

1
2
3
4
5
6
7
8
9
func min(tmp []int) int {
	minTmp := tmp[0]
	for _, v := range tmp[1:] {
		if v < minTmp {
			minTmp = v
		}
	}
	return minTmp
}

完整程式碼:

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
func nthSuperUglyNumber(n int, primes []int) int {
	ugly := make([]int, n)
	tmp := make([]int, len(primes))
	count := make([]int, len(primes))
	ugly[0] = 1
	for i := 1; i < n; i++ {
		for j, prime := range primes {
			tmp[j] = prime * ugly[count[j]]
		}
		ugly[i] = min(tmp)
		for k, v := range tmp {
			if v == ugly[i] {
				count[k]++
			}
		}
	}
	return ugly[n-1]
}
func min(tmp []int) int {
	minTmp := tmp[0]
	for _, v := range tmp[1:] {
		if v < minTmp {
			minTmp = v
		}
	}
	return minTmp
}

總結:

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

分享到