因為Ugly Number I 比較容易,跳過直接解此題,此題的Hint實在太好了,於是筆者寫了這樣子的解法:
class Solution { public: int nthUglyNumber(int n) { if(n == 0) return false; if(n == 1) return true; vector<int> ugly(n); int m2, m3, m5; ugly[0] = 1; m2 = m3 = m5 = 0; int k = 1; while(k < n) { ugly[k] = min(ugly[m2] * 2, min(ugly[m3] * 3, ugly[m5] * 5)); if( ugly[k] == ugly[m2] * 2 ) m2++; if( ugly[k] == ugly[m3] * 3 ) m3++; if( ugly[k] == ugly[m5] * 5 ) m5++; k++; } return ugly[k-1]; } };
沒有留言:
張貼留言