题目描述

找出第n大的“丑数”(ugly number)，其中，丑数是指质因数只有2、3、5的正整数。

样例

输入：10
输出：12
说明：从小到大列出丑数序列：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...，其中12是第10个丑数，所以输出12

算法1

（最小堆）$O(nlogn)$

考虑到第n个丑数一定是由前面的丑数乘上2或3或5得到的，因此可以通过对每个丑数依次乘上2、3、5得到后面的丑数，在这里采用最小堆实现。维护一个最小堆，使得最小堆中的数一定是丑数。
首先初始化堆，将1放入堆中，之后循环n次，对于第i次，利用最小堆弹出最小的数，即第i大的丑数，然后对该数乘上2、3、5得到之后的丑数放入堆中，以此类推。

时间复杂度分析：每轮需要从堆中弹出堆顶并插入新的数，因此每一轮复杂度为$O(logn)$，需要循环n轮，所以复杂度为$O(nlogn)$。

C++ 代码

class Solution {
public:
    long long nthUglyNumber(int n) {
        if(n <= 0)
            return 0;
        priority_queue<long long>pq;
        pq.push(-1);
        //由于priority queue会把最大的值放在顶端，为了实现最小堆，我把数字取负数放进去，最后取结果时再变为正数即可。
        long long lastnum = 0;//标记前一个数字
        for(int i = 1;i<=n;i++){
            long long top = pq.top();//取最小堆堆顶
            pq.pop();
            if(top == lastnum){
            //注意到不能重复，如果第i个丑数和第i-1个丑数重复了，那么跳过该丑数
                i-=1;
                continue;            
            }
            lastnum =top;
            pq.push(top*2);//将堆顶乘上2、3、5并放入堆中
            pq.push(top*3);
            pq.push(top*5);
        }
        return lastnum*-1;//注意将结果取相反数
    }
};

算法2

（动态规划 指针）$O(n)$

由于丑数的因子也必定是丑数，它一定是某个丑数乘2、3、5得到的，因此我们可以采用动态规划的思想，利用前面已经得到的丑数序列来得到之后的丑数，而问题的关键在于如何确定状态转移方程。由于小的丑数乘5不一定比大的丑数乘2要小，我们没法直接使用目前最大的丑数来乘2、3、5顺序得到更大的丑数。不过，我们可以确定的是，小的丑陋数乘2，肯定小于大的丑陋数乘2。所以我们使用三个指针，分别记录乘2、3、5得出的目前最大丑陋数，而新的丑数就是这三个目前最大丑数中最小的那个，那么就需要更新被选中的丑数的指针，获得新的三个目前最大丑数，依次类推，从而得到最终结果。

时间复杂度分析：需要维护3个指针，从1到n遍历，复杂度为$O(n)$。

C++ 代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> uglyNumbers;
        uglyNumbers.push_back(1);
        int index2 = 0;//2 3 5三个指针
        int index3 = 0;
        int index5 = 0;
        for(int i = 1;i<n;i++){
            int curMaxNum2 = uglyNumbers[index2]*2;//找出2 3 5指针指向的当前最大丑数
            int curMaxNum3 = uglyNumbers[index3]*3;
            int curMaxNum5 = uglyNumbers[index5]*5;
            int uglynum = min(min(curMaxNum2,curMaxNum3),curMaxNum5);//从当前最大丑数中选一个最小的
            if(uglynum==curMaxNum2)//更新指针
                index2++;
            if(uglynum==curMaxNum3)
                index3++;
            if(uglynum==curMaxNum5)
                index5++;
            uglyNumbers.push_back(uglynum);
        }
        return uglyNumbers[n-1];
    }
};