LeetCode OJ: 264. Ugly Number II 醜數 2

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連結 https://leetcode.com/problems/ugly-number-ii/

因為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];
    }
};

沒有留言: