摘要：這題可以使用暴力遍歷法，從開(kāi)始，對(duì)每一個(gè)數(shù)都進(jìn)行判斷，直到找到第個(gè)丑數(shù)為止。優(yōu)先隊(duì)列可以很好的滿(mǎn)足該情況。因此每個(gè)素?cái)?shù)持有的信息包括當(dāng)前對(duì)應(yīng)的丑數(shù)的下標(biāo)。

這一篇博客把ugly numbers系列的題目做一個(gè)整理。這三道題正好是一個(gè)思路的循序漸進(jìn)，所以放在一篇博客當(dāng)中。

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.

丑數(shù)是指只包含2,3,5質(zhì)因數(shù)的數(shù)。因此6,8是丑數(shù)因?yàn)?b>6=2*3,8=2*2*2，而14不是丑數(shù)因?yàn)?4包含質(zhì)因數(shù)7?，F(xiàn)在寫(xiě)一個(gè)方法判斷一個(gè)數(shù)字是否是丑數(shù)。

這題只需要將所有的2，3，5質(zhì)數(shù)消去之后，余下的質(zhì)數(shù)是不是1來(lái)進(jìn)行判斷。代碼如下：

    public boolean isUgly(int num) {
        if(num <= 0) return false;
        while(num % 2 == 0) num /= 2;
        while(num % 5 == 0) num /= 5;
        while(num % 3 == 0) num /= 3;
        return num == 1;
    }

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, and n does not exceed 1690.

這道題目在上一題定義的基礎(chǔ)上，要找到第n個(gè)丑數(shù)。

這題可以使用暴力遍歷法，從1開(kāi)始，對(duì)每一個(gè)數(shù)都進(jìn)行判斷，直到找到第n個(gè)丑數(shù)為止。但是這樣的方法效率很差。所以需要尋找一下這些數(shù)之間的規(guī)律，從而找到更好的解決方法。

這里運(yùn)用了Dynamic Programming的編程思想來(lái)解決?，F(xiàn)在我們可以將丑數(shù)完整的歸入以下三類(lèi)：

全部丑數(shù)：  1,2,3,4,5,6,8...
包含丑數(shù)2：1*2,2*2,3*2,4*2,5*2,6*2,8*2...
包含丑數(shù)3：1*3,2*3,3*3,4*3,5*3,6*3,8*3...
包含丑數(shù)5：1*5,2*5,3*5,4*5,5*5,6*5,7*5...

可以看到，每一個(gè)丑數(shù)子列上，第i位上的值等于全部丑數(shù)的第i個(gè)丑數(shù)*素?cái)?shù)。我們只需要像歸并算法中的合并方法那樣，將三個(gè)子列按照從小到大的情況合并成一個(gè)序列即可。

我們從基礎(chǔ)情況開(kāi)始推理，那么每一步的結(jié)果如下；

第0步：

全部丑數(shù)：1
包含丑數(shù)2：2
包含丑數(shù)3：3
包含丑數(shù)5：5

此時(shí)比較三個(gè)子序列，得出最小值為2，則更新全部丑數(shù)序列，并且更新包含丑數(shù)2的子序列，如下：

第1步

全部丑數(shù)：1,2
包含丑數(shù)2：2,4(2*2)
包含丑數(shù)3：3,
包含丑數(shù)5：5,

再次比較三個(gè)子序列，得出最小值為3，更新方法同上，結(jié)果如下：
第2步

全部丑數(shù)：1,2,3
包含丑數(shù)2：2,4
包含丑數(shù)3：3,6(2*3)
包含丑數(shù)5：5

按照如上方法我們就可以得出第n個(gè)丑數(shù)的值。 代碼如下

    public int nthUglyNumber(int n) {
        int idx1 = 0, idx2 = 0, idx3 = 0;
        int[] result = new int[n];
        result[0] = 1;
        for(int i = 1 ; i
313 Super ugly number
Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
這一題和上一題的變化相比，基本素?cái)?shù)從[2,3,5]變成了任意數(shù)量的有序素?cái)?shù)構(gòu)成的數(shù)組。其實(shí)本質(zhì)上思路還是一樣的，我們只需要新建一個(gè)數(shù)組來(lái)存放當(dāng)前子序列丑數(shù)對(duì)應(yīng)的所有丑數(shù)的下標(biāo)就可以了。代碼如下：
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] index = new int[primes.length];
        int[] uglyNumbers = new int[primes.length];
        System.arraycopy(primes, 0, uglyNumbers, 0, primes.length);
        
        int[] result = new int[n];
        result[0] = 1;
        for(int i = 1 ; i
當(dāng)然，這道題也可以利用特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)完成。優(yōu)先隊(duì)列可以很好的滿(mǎn)足該情況。我們先將題目中提供的所有素?cái)?shù)輸入到優(yōu)先隊(duì)列中，相當(dāng)于存入了所有的子丑數(shù)列的第一個(gè)元素。因此每個(gè)素?cái)?shù)持有的信息包括當(dāng)前對(duì)應(yīng)的丑數(shù)的下標(biāo)。之后我們可以將比較的任務(wù)交給優(yōu)先隊(duì)列的完成，我們只需從中提取最小的那個(gè)數(shù)，加到結(jié)果集中，同時(shí)別忘了更新各個(gè)子序列從而消去出現(xiàn)重復(fù)值的情況。
代碼如下：
    public int nthSuperUglyNumberHeap(int n, int[] primes) {
        int[] ugly = new int[n];

        PriorityQueue pq = new PriorityQueue<>();
        for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
        ugly[0] = 1;

        for (int i = 1; i < n; i++) {
            ugly[i] = pq.peek().val;
            while (pq.peek().val == ugly[i]) {
                Num nxt = pq.poll();
                pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
            }
        }

        return ugly[n - 1];
    }

    private class Num implements Comparable {
        int val;
        int idx;
        int p;

        public Num(int val, int idx, int p) {
            this.val = val;
            this.idx = idx;
            this.p = p;
        }

        @Override
        public int compareTo(Num that) {
            return this.val - that.val;
        }
    }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~