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 7 13 19
1 2
2
第 2 步:
2 7 13 19
1 2 7
2 4
4
第 3 步:
2 7 13 19
1 2 7 13
2 4 14
4 8
7
第 4 步:
2 7 13 19
1 2 7 13 19
2 4 14 26
4 8 28
7 14
13
其实整个丑数的产生过程就是不断的填充矩阵对角线(左下到右上)上的值，然后从所有已生成的值中挑出最小的来扩充新的一行, 但是如果直接按这种方式写代码，最终结果是超时，该算法的时间复杂度为 O(nk)，其中 n 为要找的第 n 个丑数， k 为质数数量。改进的方法是，我们按列来生成备选的数字， primes 里有多少个质数就有多少列， 初始化的时候每列数字所乘的系数都是 1，我们在生成新的数字的时候要保存每个数字属于那一列， 同时也要保存该数字所乘以的系数，而该系数其实就是上面矩阵中的最左侧那一列， 也就是所生成的数字。我们每次从生成的数字中拿出值最小的那个作为新一行的系数，同时将该数字的系数上调一级生成新的备选数字
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
pub fn nth_super_ugly_number(n: i32, primes: Vec<i32>) -> i32 {
let mut uglys = vec![1i64];
let mut heap: BinaryHeap<Reverse<(i64, i64, usize)>> = BinaryHeap::new();
for p in &primes {
heap.push(Reverse((*p as i64, *p as i64, 0)));
}
let mut count = 1;
while count < n {
let Reverse((v, p, i)) = heap.pop().unwrap();
if v != *uglys.last().unwrap() {
uglys.push(v);
count += 1;
}
heap.push(Reverse((p * uglys[i + 1], p, i + 1)));
}
return uglys[n as usize - 1] as i32;
}
}