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

這一篇博客把ugly numbers系列的題目做一個整理。這三道題正好是一個思路的循序漸進，所以放在一篇博客當中。

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ù)因為6=2*3,8=2*2*2，而14不是丑數(shù)因為14包含質(zhì)因數(shù)7。現(xiàn)在寫一個方法判斷一個數(shù)字是否是丑數(shù)。

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

    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個丑數(shù)。

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

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

全部丑數(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...

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

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

第0步：

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

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

第1步

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

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

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

按照如上方法我們就可以得出第n個丑數(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.
這一題和上一題的變化相比，基本素數(shù)從[2,3,5]變成了任意數(shù)量的有序素數(shù)構(gòu)成的數(shù)組。其實本質(zhì)上思路還是一樣的，我們只需要新建一個數(shù)組來存放當前子序列丑數(shù)對應(yīng)的所有丑數(shù)的下標就可以了。代碼如下：
    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
當然，這道題也可以利用特殊的數(shù)據(jù)結(jié)構(gòu)來完成。優(yōu)先隊列可以很好的滿足該情況。我們先將題目中提供的所有素數(shù)輸入到優(yōu)先隊列中，相當于存入了所有的子丑數(shù)列的第一個元素。因此每個素數(shù)持有的信息包括當前對應(yīng)的丑數(shù)的下標。之后我們可以將比較的任務(wù)交給優(yōu)先隊列的完成，我們只需從中提取最小的那個數(shù)，加到結(jié)果集中，同時別忘了更新各個子序列從而消去出現(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;
        }
    }

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