作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处
题目描述：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围：0≤n≤2000
要求：空间复杂度 O(n) ， 时间复杂度 O(n)
示例：
输入：
7
返回值：
8
解题思路：
本题考察算法思维。两种解题思路：
1)优先队列-最小堆
丑数是含质因子2、3、5的数，从1开始，1乘这三个因数得到的数就是丑数，以此类推，丑数乘因数也是丑数。考虑到这样操作可能会有重复，所以借助map完成去重。再构建优先队列-小顶堆往里面塞入丑数，放入的过程会自动进行排序，排序复杂度在O(log2n)。
假设获取前n个丑数，就进行n次循环，每次循环将最小的丑数弹出，并放入新的丑数，放入的时候还需要进行重复性判断。
综合下来，算法时间复杂度为O(nlog2n)。
2)动态规划
丑数1 2 3 4 5 6 8 9 10等等，每个丑数一定是前面某个数的235倍数，可结合动态规划思想，设置三个步进下标ijk，将已知丑数依次乘235得到后续丑数，在此过程中还需要确保丑数是从小到大放入容器的，即进行最小值比较。
为了直观些，简单模拟下前面几步的流程：
1）开始ijk均为0，则从数字1开始，丑数后续依次为2 3 5，其中2最小，则i升为1。
2）i为1，即第二个丑数2，用2的2倍也就是4和3 5比较，此时3最小，则j升为1。
3）i和j为1，即用第二个丑数2的2倍3倍，即4和6，和5比较，此时4最小，则i继续升为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步可看到全局规律，ijk是从前往后慢慢推进的，结合了动态规划的思想，后续步进以前面为基准，动态扩展后续丑数
该算法时间复杂度为O(n)，也是题目理想解法。
测试代码：
1)优先队列-最小堆
#include <queue>
class Solution {
public:
// 获取丑数
int GetUglyNumber_Solution(int index) {
// 判空
if(index == 0){
return 0;
}
// 定义因数集合
vector<int> factors = { 2, 3, 5};
// 定义哈希表
unordered_map<long, bool> um;
// 定义优选队列-小顶堆
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倍数的值
long temp = result * factors[j];
// 只存放非重复值
if(um.find(temp) == um.end()){
um[temp] = true;
pq.push(temp);
}
}
}
return int(result);
}
};2)动态规划
#include <queue>
class Solution {
public:
// 获取丑数
int GetUglyNumber_Solution(int index) {
// 判空
if(index == 0){
return 0;
}
// 定义丑数集合
vector<int> uglyNums = { 1 };
// 循环按规律找到所有丑数
int i = 0, j = 0, k = 0;
int t;
for(t = 0; t < index; ++t){
// ijk表示已知丑数乘235的进度
// 举例说明
// 1）开始ijk均为0，则从数字1开始，丑数后续依次为2 3 5，其中2最小，则i升为1
// 2）i为1，即第二个丑数2，用2的2倍也就是4和3 5比较，此时3最小，则j升为1
// 3）i和j为1，即用第二个丑数2的2倍3倍，即4和6，和5比较，此时4最小，则i继续升为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步可看到全局规律，ijk是从前往后慢慢推进的，结合了动态规划的思想，后续步进以前面为基准，动态扩展后续丑数
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];
}
};