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 ≤ 106, 0 < primes[i] < 1000. (4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
s思路： 1. 看到这题，就想起前几天做的， 264. Ugly Number II http://blog.csdn.net/xinqrs01/article/details/55043564 2. 这道题，如果还这样做的话，就没必要出这道题了，为什么？因为264这道题是prime factor只有3个，规模小，而这道题prime factor是一个变量k,k可以等于100。264的解题复杂度是o(3*n)==o(n)，如果这道题还如法炮制，就是o(k*n),这就显得无趣！ 3. 从这个角度看，应该能猜到由于问题规模变大了，有各种冗余存在了，因此起始解题的复杂度并不是和问题的复杂度线性增加滴，所以有可能找到o(n*lgk). 4. lgk也容易得到嘛，你看给的factor都是正数，还递增，那就是说每次找下一个丑数的时候，不用一个一个比较，而是利用排好序的前提，用divide and conquer或一些数据结构，例如：heap或set来做就可以啦 5. 想问题，从结果入手，只是换了一个角度罢了，问题还是这么个问题！ 6. 你看，排好序的话，问题复杂度就降低这么多，所以说排序多么重要！ 7. 这里记录一下刚才想的时候，确实脑袋里闪过用heap念头时，马上就抓住这个念头了，但是发现不知道如何在heap里面存数据的时候，几乎快放弃了，最后左尝试右尝试发现用pair
//方法１：用heap,复杂度o(n*lgk)class Solution {public: struct compare{ bool Operator()(pair<int,pair<int,int>>&a,pair<int,pair<int,int>>&b){ return a.first>b.first; } }; int nthSuperUglyNumber(int n, vector<int>& primes) { // vector<int> res(n,1); priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,compare> pq; for(int p:primes){ pq.push(make_pair(p,make_pair(p,0))); } int idx=1; while(idx<n){ auto cur=pq.top(); pq.pop(); if(cur.first>res[idx-1]) //bug:写的时候，太激动，脑袋里面都没有想起有重复的话怎么办 //但在纸上画的时候是看到这个重复的 res[idx++]=cur.first; cur.second.second+=1; cur.first=cur.second.first*res[cur.second.second]; pq.push(cur); //cout<<res[idx-1]<<endl; } return res[n-1]; }};新闻热点
疑难解答
