思路：

由题目中给到的信息：

丑数仅由2、3、5的因子组成
1是第一个丑数

现在要寻找第n个丑数，最简单值观的方法莫过于从1开始依次往后递增加1，判断每个数是否将2除尽、3除尽、5除仅为1且不含余数，若是则丑数加1，继续往后找。此方法问题在于随着数字不断增大，要除尽2、3 、5需要多次循环，且中间会计算很多非丑数，十分浪费时间，也确实会超时。因此需要换思路。

方法一：235乘法 由上方列出的条件可知，丑数由1乘上2或3或5，并在这个基础上不断乘2或3或5组成，且因其是递增的，我们便可以从开始，给前面找到丑数乘上2，3，5，且要它们中大于最后一个找到的丑数中的最小值。比如：第一个丑数1 1 x 2 = 2 1 x 3 = 3 1 x 5 = 5 则第二个丑数为2，继续便是： 1 x 2 = 2，2 x 2 = 4 1 x 3 = 3 1 x 5 = 5 则第三个丑数为3，继续便是： 1 x 2 = 2，2 x 2 = 4 1 x 3 = 3，2 x 3 = 6 1 x 5 = 5 第四个丑数为4 ……………… 代码如下：

class Solution {
public:
    int findMin(int x, int y, int z){  //寻找三个数中的最小值
        int res = x; 
        res = y < res ? y : res;
        res = z < res ? z : res;
        return res;
    }
    int GetUglyNumber_Solution(int index) {
        if(index == 0)
            return 0; //第一个丑数为1，第0个没有
        vector<int> num;
        num.push_back(1);
        int count = 1; //记录第几个丑数
        int x = 0, y = 0, z = 0;
        while(count < index){
            for(int i = 0 ; i < count; i++){  //找到与2相乘第一个大于num中末尾的数
			    if(num[i] * 2 > num[count - 1]){
				    x = num[i] * 2; 
				        break;
			    }
		    }
            for(int i = 0 ; i < count; i++){  //找到与3相乘第一个大于num中末尾的数
			    if(num[i] * 3 > num[count - 1]){
				    y = num[i] * 3; 
				        break;
			    }
		    }
            for(int i = 0 ; i < count; i++){  //找到与5相乘第一个大于num中末尾的数
			    if(num[i] * 5 > num[count - 1]){
				    z = num[i] * 5; 
				        break;
			    }
		    }
            num.push_back(findMin(x, y, z));//将找到的最小值加入数组
            count++;
        }
        return num[count - 1];
    }
};

复杂度分析：

时间复杂度：O(n^2)，双层for循环
空间复杂度：O(n)，vector存储每一个丑数

方法二：235乘法改进——贪心思想 上述方法虽然比暴力判断每一个数是否是丑数要节省不少时间，但是我们依然可以发现，它重复计算了很多前面部分——那部分肯定不会再比最后一个已知丑数大了，因此我们可以采取方法避免：用下标递增来表示，当已经运算过后就让下标永久加1. 图片说明

class Solution {
public:
    int findMin(int x, int y, int z){  //寻找三个数中的最小值
        int res = x; 
        res = y < res ? y : res;
        res = z < res ? z : res;
        return res;
    }
    int GetUglyNumber_Solution(int index) {
        if(index == 0)
            return 0; //第一个丑数为1，第0个没有
        vector<int> num;
        num.push_back(1);
        int count = 1; //记录第几个丑数
        int x = 0, y = 0, z = 0; //x,y,z分别代表要乘上2 3 5的下标
        while(count < index){
            num.push_back(findMin(num[x] * 2, num[y] * 3, num[z] * 5));
            count++;
            if(num[count - 1] == num[x] * 2)
                x++; //由2与已知丑数相乘得到的丑数，那该下标及之前的在2这里都用不上了
            if(num[count - 1] == num[y] * 3)
                y++; //由3与已知丑数相乘得到的丑数，那该下标及之前的在3这里都用不上了
            if(num[count - 1] == num[z] * 5)
                z++; //由5与已知丑数相乘得到的丑数，那该下标及之前的在5这里都用不上了
        }
        return num[count - 1];
    }
};

复杂度分析：

时间复杂度：O(n)，只遍历一次
空间复杂度：O(n)，存储丑数的vector

题解 | #丑数#

思路：