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. 這道題，如果還這樣做的話，就沒必要出這道題了，為什么？因?yàn)?64這道題是prime factor只有3個(gè)，規(guī)模小，而這道題prime factor是一個(gè)變量k,k可以等于100。264的解題復(fù)雜度是o(3*n)==o(n)，如果這道題還如法炮制，就是o(k*n),這就顯得無趣！ 3. 從這個(gè)角度看，應(yīng)該能猜到由于問題規(guī)模變大了，有各種冗余存在了，因此起始解題的復(fù)雜度并不是和問題的復(fù)雜度線性增加滴，所以有可能找到o(n*lgk). 4. lgk也容易得到嘛，你看給的factor都是正數(shù)，還遞增，那就是說每次找下一個(gè)丑數(shù)的時(shí)候，不用一個(gè)一個(gè)比較，而是利用排好序的前提，用divide and conquer或一些數(shù)據(jù)結(jié)構(gòu)，例如：heap或set來做就可以啦 5. 想問題，從結(jié)果入手，只是換了一個(gè)角度罷了，問題還是這么個(gè)問題！ 6. 你看，排好序的話，問題復(fù)雜度就降低這么多，所以說排序多么重要！ 7. 這里記錄一下剛才想的時(shí)候，確實(shí)腦袋里閃過用heap念頭時(shí)，馬上就抓住這個(gè)念頭了，但是發(fā)現(xiàn)不知道如何在heap里面存數(shù)據(jù)的時(shí)候，幾乎快放棄了，最后左嘗試右嘗試發(fā)現(xiàn)用pair
//方法１：用heap,復(fù)雜度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:寫的時(shí)候，太激動(dòng)，腦袋里面都沒有想起有重復(fù)的話怎么辦 //但在紙上畫的時(shí)候是看到這個(gè)重復(fù)的 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]; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
