Ugly Number II

NO IMAGE

題目

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

方法一

思路

由於上一篇文章《Ugly Number》中實現了判斷一個正整數是否是Ugly Number的功能,所以,我們從1開始,逐一判斷正整數是否是Ugly Number,如果是,i 加一,直到 i 等於 n 即可。

這個演算法的缺點是開銷太大,我們不僅需要找出第n個Ugly Number之前的所有Ugly Number,也需要找出第n個Ugly Number之前的所有Ugly Number。方法二的思路是隻要找到第n個Ugly Number之前的所有Ugly Number即可。

程式碼

class Solution {
public:
    int nthUglyNumber(int n) {
        int i = 0;
        int num = 1;
        while (i != n)
        {
            if (isUgly(num) )
            {
                i  ;
            }
            num  ;
        }
        return num - 1;
    }
    
    bool isUgly(int num) {
        if (num <= 0)
        {
            return false;
        }
        
        if (1 == num)
        {
            return true;
        }
            
        int pNum = num;
        
        while (pNum % 5 == 0)
        {
            pNum /= 5;
        }
        while (pNum % 3 == 0)
        {
            pNum /= 3;
        }
        while (pNum % 2 == 0)
        {
            pNum /= 2;
        }
        
        if (pNum == 1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

方法二

思路

如何只找Ugly Number呢?我們從它的概念入手。Ugly Number的prime factors只有1,2,3,5,也就是說所有的Ugly Number都是由一個或多個1,2,3,5的乘積組成,這樣,我們就從1開始派生,對於目前已知的Ugly Number(初始狀態Ugly Number只有一個“1”),讓它分別乘以2,3,5,得到的數還是Ugly Number。

考慮到我們需要從小到大提取前n個Ugly Number,set 容器很符合我們的要求,它不僅能自動排序,而且能遮蔽掉相同元素。

看!下面程式碼就是這麼簡潔!

程式碼

class Solution {
public:
    long nthUglyNumber(int n) {
        int i = 1;
        set<long> s;
        s.insert(1);
        while (i < n)
        {
            long first = *s.begin();
            s.insert(first * 2);
            s.insert(first * 3);
            s.insert(first * 5);
            
            s.erase(first);
            
            i  ;
        }
        
        return *s.begin();
    }
};

總結

此題一個坑爹的地方是:網站給出的函式的返回值明明是int型,測試資料卻用到了long型,結果因為資料越界報出“Wrong Answer”的錯誤,這怪我嘍?通過的方法是將 nthUglyNumber 函式的返回值改為long即可。