LeetCode每日一题(313. Super Ugly Number)

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32

Explanation: [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].

Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1

Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

Constraints:

• 1 <= n <= 105
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• primes[i] is guaranteed to be a prime number.
• All the values of primes are unique and sorted in ascending order.

---

我们把丑数的生成过程用矩阵的形式表达出来:

第 0 步:

	2	7	13	19

1
1
2
3

第 1 步:

	2	7	13	19

1	2

2
1
2
3
4
5

第 2 步:

	2	7	13	19

1 	2 	7

2 	4

4
1
2
3
4
5
6
7

第 3 步:

	2	7	13	19

1 	2 	7	13

2 	4	14

4	8

7
1
2
3
4
5
6
7
8
9

第 4 步:

	2	7	13	19

1 	2 	7	13	19

2 	4	14	26

4	8	28

7	14

13
1
2
3
4
5
6
7
8
9
10
11

其实整个丑数的产生过程就是不断的填充矩阵对角线(左下到右上)上的值，然后从所有已生成的值中挑出最小的来扩充新的一行, 但是如果直接按这种方式写代码，最终结果是超时，该算法的时间复杂度为 O(nk)，其中 n 为要找的第 n 个丑数， k 为质数数量。改进的方法是，我们按列来生成备选的数字， primes 里有多少个质数就有多少列， 初始化的时候每列数字所乘的系数都是 1，我们在生成新的数字的时候要保存每个数字属于那一列， 同时也要保存该数字所乘以的系数，而该系数其实就是上面矩阵中的最左侧那一列