描述

这是一篇针对初学者的题解。共用2种方法解决。
知识点：队列，动态规划
难度：2星

题解

题目抽象：定义一个数只包含质因子2,3，5的数，称为丑数，寻找第N个丑数。

方法一：暴力方法

根据丑数的定义，可以直接判断数num是否为丑数，然后寻找第N个。判断某个数num是否为丑数，最慢需要num/2次，一个判断N个，所以直接复杂度为O(N^2),具体实现比较简单，可自行实现。

方法二：队列

假设方法一是正向思维，也就是判断某个数是否为丑数，那么方法二属于逆向思维，已知一个丑数，那么它的2倍，3倍，5倍，都是丑数。我们可以用三个队列来分别存2倍的丑数，3倍的丑数，5倍的丑数。
算法步骤：

1. 初始化三个队列,q2,q3,q5分别存2倍的丑数，3倍的丑数，5倍的丑数
2. 选取q2,q3,q5队列的头部值的最小值，最小值的2倍放入q2, 3倍放入q3, 5倍放入q5
3. 循环步骤2，直到找到第N个丑数。

代码

class Solution {
public:
   int GetUglyNumber_Solution(int index) {
        if (index == 0) return 0; 
        queue<int> q2, q3, q5;
        q2.push(2), q3.push(3), q5.push(5);
        int ret = 1;
        for (int i = 1; i <= index; ++i)
        {
            int val2 = q2.front();
            int val3 = q3.front();
            int val5 = q5.front();

            ret = min(val2, min(val3, val5));

            if (ret == val2)
            {
                q2.pop();
                q2.push(2 * ret);
                q3.push(3 * ret);
            }
            else if (ret == val3)
            {
                q3.pop();
                q3.push(3 * ret);
            }
            else
            {
                q5.pop();
            }

            q5.push(5 * ret);
        }

        return ret;
    }
};

时间复杂度：O(N)
空间复杂度：O(N)

方法二：动态规划

动态规划需要弄清两个问题：

1. 状态的定义：dp[i]表示第i个丑数是多少
2. 状态转移方程：dp[i] =