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
.
Example:
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 givenprimes
=[2,7,13,19]
of size 4.
Note:
1
is a super ugly number for any givenprimes
.- The given numbers in
primes
are in ascending order. - 0 <
k
≤ 100, 0 <n
≤ 106, 0 <primes[i]
< 1000. - The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
A:
动态规划,ugly number一定是由一个较小的ugly number乘以2,3或5得到的。
先开一个数组记录所有的ugly number。
然后开一个变量数组A,一开始都是零,指向数组的第0位。 A[i]是ugly number的index,
A[i] * primes[i] > current ugly number
每一次取Min(A[i] * primes[i]),找到这个数之后,对应的A[i]加一,指向数组的下一位。
Mistakes:class Solution { public: int nthSuperUglyNumber(int n, vector<int>& primes) { vector<int> list{1}; int m = primes.size(); vector<int> Index(m, 0); while(list.size()<n){ vector<int> V; int last = list.back(); for(int i =0;i<m; i++){ // for each prime number while(list[Index[i]]*primes[i] <= last){ Index[i]++; } V.push_back(list[Index[i]]*primes[i]); } list.push_back(*min_element(V.begin(), V.end())); } return list[n-1]; } };
第二遍的时候,
1: 在while中,以为不会有相等的。 因此只用了 < ,这样是不对的。
2: 如果res 改成list, 会超时
****************用 min-heap 会超时****************
public class Solution { public int nthSuperUglyNumber(int n, int[] primes) { Queue<Integer> minHeap = new PriorityQueue(n*primes.length,new Comparator<Integer>(){ public int compare(Integer a, Integer b){ return a-b; } }); minHeap.add(1); Set<Integer> set = new HashSet(); int lastVal = 0, count = 0; while(count < n){ int val = minHeap.poll(); for(int i =0;i<primes.length; i++) if(val <= Integer.MAX_VALUE / primes[i] && !set.contains(val*primes[i])){ minHeap.add(val * primes[i]); set.add(val* primes[i]); } count ++; lastVal = val; } return lastVal; } }
No comments:
Post a Comment