JZ49 醜數

題目

我們先看到題目，把只包含質因數2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含質因數7。 習慣上我們把1當做是第一個醜數。

方法1：質因數分解（暴力）

思路

演算法實現

• 一個很朴素的做法
• 從1~n每次+1，一直枚舉，直到找到地N個醜數為止
• 那麼還有一個待解決的問題，如何判斷當前數字是不是醜數呢？
• 我們總結一下醜數的性質：只能分解為2,3,5的如乾次冪相乘的數，即設第個醜數為，則 res = 2*x + 3*y + 5*z
• 那麼我們只需要通過質因數分解，判斷他分解2,3,5後，是否為1，如果為1，則說明沒有其他的因數，否則則有其他因數，那麼他就不是一個醜數

問題
當輸入數過大時，需要的時間會很長，所以此方法不行

代碼

package mid.JZ49醜數;

import java.util.ArrayList;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        int current = 1;
        ArrayList<Integer> res = new ArrayList<>();
        res.add(1);
        while(true) {
            if (res.size() == index) {
                return res.get(res.size() - 1);
            }

            current++;

            if (check(current)) {
                res.add(current);
            }
        }
    }
    public boolean check(int num) {
        while(num % 2 == 0) num /= 2;
        while(num % 3 == 0) num /= 3;
        while(num % 5 == 0) num /= 5;
        return num == 1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().GetUglyNumber_Solution(1500));
    }
}

方法2

思路

• 有了上面的定義我們就可以知道，醜數的形式就是2x3y5z，所以我們可以定義一個數組res，存儲第n個醜數。
• 因為我們要將醜數按從小到大的順序排序，所以我們就得將對應的醜數放在對應的下標位置，小的放前面。
• 這個時候上面我們的出來的醜數的格式就起作用了，醜數的形式無非就是這樣2x3y5z，所以我們就將res[n]去乘以 2、3、5，然後比較出最小的那個，就是我們當前的下一個醜數了。

代碼

package mid.JZ49醜數;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 6) return index;
        int x = 0, y = 0, z = 0;
        int[] res = new int[index];

        res[0] = 1;

        for (int i = 1; i < index; i++) {
            res[i] = Math.min(res[x]*2, Math.min(res[y]*3, res[z]*5));

            if (res[i] == res[x]*2) x++;
            if (res[i] == res[y]*3) y++;
            if (res[i] == res[z]*5) z++;
        }

        return res[index - 1];
    }
}