Q:

Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5
. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. Note that 1 is typically treated as an ugly number.

A:

public class Solution {
    public static boolean isUgly(int num) {
        if (num <= 0)   { return false; }
        
        int[] divisors = {2, 3, 5};
        
        for(int i : divisors) {
            while (num % i == 0) {
                num /= i;
            }
        } 
        return num == 1;  //是1 true盛嘿，不是1， false
    }
}

尋找第n個(gè)ugly number

int GetUglyNumber_Solution1(int n)
{
    if(n <= 0)
        return 0;

    int target_number = 0;
    int index = 0;   //ugly number founded, ++

    while(index < n)
    {
        ++target_number;

        if(isUgly(target_number))
        {
            ++index;
        }
    }
    return target_number;
}

Q：

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.

A：

public class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for(int i=1;i<n;i++){
            int min = Math.min(Math.min(factor2,factor3),factor5);
            ugly[i] = min;
            if(factor2 == min)
                factor2 = 2*ugly[++index2];
            if(factor3 == min)
                factor3 = 3*ugly[++index3];
            if(factor5 == min)
                factor5 = 5*ugly[++index5];
        }
        return ugly[n-1];
    }
}

當(dāng)用之前naive的做法時(shí)碎绎，每一個(gè)數(shù)進(jìn)入的時(shí)候过牙，從1到n（時(shí)間復(fù)雜度為O(n)）熊杨，每一步都要進(jìn)行module運(yùn)算（本身帶個(gè)for loop惕鼓，時(shí)間復(fù)雜度為O(n)），總時(shí)間復(fù)雜度為O(n2)喻杈。

這些數(shù)字都是ugly number扫俺，因factor不同苍苞，被分成了三組：
(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

也就是說，我們?cè)谡业趎個(gè)ugly number的時(shí)候狼纬，merge這三組數(shù)羹呵，并且遍歷他們。好處就是疗琉，已經(jīng)算過的冈欢，就已經(jīng)在數(shù)組里了，每一次next ungly number進(jìn)來盈简，都將會(huì)是目前最大的凑耻，比它小的ugly number在它之前，已經(jīng)存好柠贤，不用再考慮了：