[每日一道小算法（十五）] [窮舉] 醜數（劍指offer習題）

前言：

最近也在看劍指offer上面的習題，有些思路很新奇，是以就再次做一下記錄。

題目描述

把隻包含質因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含質因子7。 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第N個醜數。

解題思路

方法一

方法二

代碼樣例

方法一

package com.asong.leetcode.UglyNum;

/**
 * 醜數：下面這是一個個不好的解決辦法，但是想起來很簡單
 * isUgly 用來判斷這個數是不是醜數：如果他能被2整除，就一直除，如果能被3整除，就一直除，如果能被5整出，就一直除，最後num變為1，則代表是醜數。
 * GetUglyNumber_Solution 這裡從1開是一個一個的判斷是不是醜數，并儲存最大值。
 */
public class Solution {
    /**
     * 用來判斷是不是醜數
     * @param num 要判斷的數字
     * @return
     */
    public static boolean isUgly(int num)
    {
        while(num % 2 == 0)
        {
            num /= 2;
        }
        while(num % 3 == 0)
        {
            num /= 3;
        }
        while (num % 5 == 0)
        {
            num /= 5;
        }
        return (num==1)?true:false;
    }

    /**
     * 得到第index個醜數
     * @param index
     * @return
     */
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0)
        {
            return 0;
        }
        int number = 0; //從0開始的數字
        int uglyFound = 0; //找到的醜數計數 到達index截至
        while(uglyFound < index)
        {
            ++number;
            if(isUgly(number))
            {
                uglyFound++;
            }
        }

        return number;
    }
}      

方法二

package com.asong.leetcode.UglyNum;

import java.util.Vector;

public class SolutionNice {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0)
        {
            return 0;
        }
        int[] uglyNumbers = new int[index]; //建立數組儲存醜數
        uglyNumbers[0] = 1; //第一個醜數
        int nextUglyIndex = 1; //作為索引
        int ugly2=0,ugly3=0,ugly5=0; //用來儲存每個醜數的最小值在數組中的位置
        for (nextUglyIndex = 1 ;nextUglyIndex < index ; nextUglyIndex++)
        {
            uglyNumbers[nextUglyIndex]=Math.min(uglyNumbers[ugly2]*2,Math.min(uglyNumbers[ugly3]*3,uglyNumbers[ugly5]*5));
            if(uglyNumbers[nextUglyIndex] == uglyNumbers[ugly2]*2)
            {
                ugly2++;
            }
            if(uglyNumbers[nextUglyIndex] == uglyNumbers[ugly3]*3)
            {
                ugly3++;
            }
            if(uglyNumbers[nextUglyIndex] == uglyNumbers[ugly5]*5)
            {
                ugly5++;
            }
        }
        return uglyNumbers[index-1];
    }
}