題目：我們把只包含因子2东且、3 和5 的數(shù)稱作丑數(shù)（Ugly Number）截珍。求從小到大的順序的第1500個(gè)丑數(shù)论熙。

代碼如下：

解法1：

package demo;

/**
 * 丑數(shù)
 * 
 * @author xiangdonglee
 *
 */
public class Test34_1 {
    /**
     * 判斷一個(gè)數(shù)是否是丑數(shù)（只有2螃成、3犹菱、5因子）
     * 
     * @param num
     *            待判斷的數(shù)朗儒，非負(fù)
     * @return true：是丑數(shù)颊乘；false：不是丑數(shù)
     */
    private 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;
    }

    /**
     * 找第index個(gè)丑數(shù)
     * 
     * @param index
     *            第index個(gè)丑數(shù)
     * @return 對(duì)應(yīng)的丑數(shù)值
     */
    public static int getUglyNumber1(int index) {
        if (index <= 0) {
            return 0;
        }
        int num = 0;
        int uglyFound = 0;
        while (uglyFound < index) {
            num++;
            if (isUgly(num)) {
                uglyFound++;
            }
        }
        return num;
    }

    public static void main(String[] args) {
        System.out.println("Solution 1:");
        test1();
    }

    private static void test1() {
        System.out.println("第1個(gè)丑數(shù):" + getUglyNumber1(1));
        System.out.println("第2個(gè)丑數(shù):" + getUglyNumber1(2));
        System.out.println("第3個(gè)丑數(shù):" + getUglyNumber1(3));
        System.out.println("第4個(gè)丑數(shù):" + getUglyNumber1(4));
        System.out.println("第5個(gè)丑數(shù):" + getUglyNumber1(5));
        System.out.println("第6個(gè)丑數(shù):" + getUglyNumber1(6));
        System.out.println("第7個(gè)丑數(shù):" + getUglyNumber1(7));
        System.out.println("第8個(gè)丑數(shù):" + getUglyNumber1(8));
        System.out.println("第9個(gè)丑數(shù):" + getUglyNumber1(9));
        System.out.println("第10個(gè)丑數(shù):" + getUglyNumber1(10));
        System.out.println("第11個(gè)丑數(shù)" + getUglyNumber1(11));
        System.out.println("第1500個(gè)丑數(shù)" + getUglyNumber1(1500));
        System.out.println("第0個(gè)丑數(shù)" + getUglyNumber1(0));
    }
}

運(yùn)行結(jié)果

解法2：

package demo;

public class Test34_2 {
    /**
     * 找第index個(gè)丑數(shù)
     * 
     * @param index
     *            第index個(gè)丑數(shù)
     * @return 對(duì)應(yīng)的丑數(shù)值
     */
    public static int getUglyNumber2(int index) {
        if (index <= 0) {
            return 0;
        }
        int[] pUglyNumbers = new int[index];
        pUglyNumbers[0] = 1;
        int nextUglyIndex = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        while (nextUglyIndex < index) {
            int min = min(pUglyNumbers[p2] * 2, pUglyNumbers[p3] * 3, pUglyNumbers[p5] * 5);
            pUglyNumbers[nextUglyIndex] = min;
            while (pUglyNumbers[p2] * 2 <= pUglyNumbers[nextUglyIndex]) {
                p2++;
            }
            while (pUglyNumbers[p3] * 3 <= pUglyNumbers[nextUglyIndex]) {
                p3++;
            }
            while (pUglyNumbers[p5] * 5 <= pUglyNumbers[nextUglyIndex]) {
                p5++;
            }
            nextUglyIndex++;
        }
        return pUglyNumbers[nextUglyIndex - 1];
    }

    private static int min(int i, int j, int k) {
        int min = i < j ? i : j;
        return min < k ? min : k;
    }

    public static void main(String[] args) {
        System.out.println("Solution 2:");
        test2();
    }

    private static void test2() {
        System.out.println("第1個(gè)丑數(shù):" + getUglyNumber2(1));
        System.out.println("第2個(gè)丑數(shù):" + getUglyNumber2(2));
        System.out.println("第3個(gè)丑數(shù):" + getUglyNumber2(3));
        System.out.println("第4個(gè)丑數(shù):" + getUglyNumber2(4));
        System.out.println("第5個(gè)丑數(shù):" + getUglyNumber2(5));
        System.out.println("第6個(gè)丑數(shù):" + getUglyNumber2(6));
        System.out.println("第7個(gè)丑數(shù):" + getUglyNumber2(7));
        System.out.println("第8個(gè)丑數(shù):" + getUglyNumber2(8));
        System.out.println("第9個(gè)丑數(shù):" + getUglyNumber2(9));
        System.out.println("第10個(gè)丑數(shù):" + getUglyNumber2(10));
        System.out.println("第11個(gè)丑數(shù):" + getUglyNumber2(11));
        System.out.println("第1500個(gè)丑數(shù):" + getUglyNumber2(1500));
        System.out.println("第0個(gè)丑數(shù):" + getUglyNumber2(0));
    }
}

運(yùn)行結(jié)果

來(lái)源：http://blog.csdn.net/derrantcm/article/details/46753255