作者：翟天保Steven
版權聲明：著作權歸作者所有，商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處

題目描述：

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

數(shù)據(jù)范圍：0≤n≤2000

要求：空間復雜度 O(n)?， 時間復雜度 O(n)

示例：

輸入：

7

返回值：

8

解題思路：

本題考察算法思維。兩種解題思路：

1)優(yōu)先隊列-最小堆

? ? ? ?丑數(shù)是含質因子2、3、5的數(shù)，從1開始，1乘這三個因數(shù)得到的數(shù)就是丑數(shù)，以此類推，丑數(shù)乘因數(shù)也是丑數(shù)。考慮到這樣操作可能會有重復，所以借助map完成去重。再構建優(yōu)先隊列-小頂堆往里面塞入丑數(shù)，放入的過程會自動進行排序，排序復雜度在O(log2n)。

? ? ? ?假設獲取前n個丑數(shù)，就進行n次循環(huán)，每次循環(huán)將最小的丑數(shù)彈出，并放入新的丑數(shù)，放入的時候還需要進行重復性判斷。

? ? ? ?綜合下來，算法時間復雜度為O(nlog2n)。

2)動態(tài)規(guī)劃

? ? ? ?丑數(shù)1 2 3 4 5 6 8 9 10等等，每個丑數(shù)一定是前面某個數(shù)的235倍數(shù)，可結合動態(tài)規(guī)劃思想，設置三個步進下標ijk，將已知丑數(shù)依次乘235得到后續(xù)丑數(shù)，在此過程中還需要確保丑數(shù)是從小到大放入容器的，即進行最小值比較。

? ? ? ?為了直觀些，簡單模擬下前面幾步的流程：

1）開始ijk均為0，則從數(shù)字1開始，丑數(shù)后續(xù)依次為2 3 5，其中2最小，則i升為1。

2）i為1，即第二個丑數(shù)2，用2的2倍也就是4和3 5比較，此時3最小，則j升為1。

3）i和j為1，即用第二個丑數(shù)2的2倍3倍，即4和6，和5比較，此時4最小，則i繼續(xù)升為2。

4）i為2，j為1，k為0，用3的2倍、2的3倍、1的5倍比較，即6 6 4，此時5最小，則k升為1。

5）i為2，j為1，k為1，用3的2倍、2的3倍，2的5倍比較，即6 6 10，此時6最小，i和j同時升1。

? ? ? ?從上述5步可看到全局規(guī)律，ijk是從前往后慢慢推進的，結合了動態(tài)規(guī)劃的思想，后續(xù)步進以前面為基準，動態(tài)擴展后續(xù)丑數(shù)

? ? ? ?該算法時間復雜度為O(n)，也是題目理想解法。

測試代碼：

1)優(yōu)先隊列-最小堆

#include <queue>
class Solution {
public:
    // 獲取丑數(shù)
    int GetUglyNumber_Solution(int index) {
        // 判空
        if(index == 0){
            return 0;
        }
        // 定義因數(shù)集合
        vector<int> factors = { 2, 3, 5};
        // 定義哈希表
        unordered_map<long, bool> um;
        // 定義優(yōu)選隊列-小頂堆
        priority_queue<long, vector<long>, greater<>> pq;
        // 放入1
        um[long(1)] = true;
        pq.push(long(1));
        long result = 0;
        for(int i = 0; i < index; ++i){
            // 每次取頂，也就是最小值，彈出
            result = pq.top();
            pq.pop();
            for(int j = 0; j < 3; ++j){
                // 存入235倍數(shù)的值
                long temp = result * factors[j];
                // 只存放非重復值
                if(um.find(temp) == um.end()){
                    um[temp] = true;
                    pq.push(temp);
                }
            }
        }
        return int(result);
    }
};

2)動態(tài)規(guī)劃文章來源地址http://www.zghlxwxcb.cn/news/detail-777498.html

#include <queue>
class Solution {
public:
    // 獲取丑數(shù)
    int GetUglyNumber_Solution(int index) {
        // 判空
        if(index == 0){
            return 0;
        }
        // 定義丑數(shù)集合
        vector<int> uglyNums = { 1 };
        // 循環(huán)按規(guī)律找到所有丑數(shù)
        int i = 0, j = 0, k = 0;
        int t;
        for(t = 0; t < index; ++t){
            // ijk表示已知丑數(shù)乘235的進度
            // 舉例說明
            // 1）開始ijk均為0，則從數(shù)字1開始，丑數(shù)后續(xù)依次為2 3 5，其中2最小，則i升為1
            // 2）i為1，即第二個丑數(shù)2，用2的2倍也就是4和3 5比較，此時3最小，則j升為1
            // 3）i和j為1，即用第二個丑數(shù)2的2倍3倍，即4和6，和5比較，此時4最小，則i繼續(xù)升為2
            // 4）i為2，j為1，k為0，用3的2倍、2的3倍、1的5倍比較，即6 6 4，此時5最小，則k升為1
            // 5）i為2，j為1，k為1，用3的2倍、2的3倍，2的5倍比較，即6 6 10，此時6最小，i和j同時升1
            // 從上述5步可看到全局規(guī)律，ijk是從前往后慢慢推進的，結合了動態(tài)規(guī)劃的思想，后續(xù)步進以前面為基準，動態(tài)擴展后續(xù)丑數(shù)
            int num2 = uglyNums[i] * 2;
            int num3 = uglyNums[j] * 3;
            int num5 = uglyNums[k] * 5;
            int minNum = min(num2, min(num3, num5));
            uglyNums.push_back(minNum);
            if(minNum == num2){
                i++;
            }
            if(minNum == num3){
                j++;
            }
            if(minNum == num5){
                k++;
            }
        }
        return uglyNums[t - 1];
    }
};

到了這里，關于劍指offer(C++)-JZ49：丑數(shù)(算法-其他)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！