丑数
C++，丑数，质因数。
网上很多代码讲了怎么获得下一个最小的丑数，就是利用前面的每一个丑数分别*2，*3，*5，然后选出最小的那个。按照这个描述，只能每次将之前所有的丑数都和2、3、5乘一遍，那复杂度就是O(n)，可网上写出来的代码都是O(n)的，你说气人不气人？？？
看了一会自己看懂了，把思路讲一下：
- 首先每个丑数都是由之前的丑数乘(
*2，*3，*5)出来的； - 为了得到所有丑数，我们可以从1开始，将每个丑数都乘2、3、5，然后排序，取第k个数，返回，但是这样做复杂度太大了；
- 其实不仅每个丑数都是由之前的丑数乘出来的，而且每个丑数乘以2、3、5页必是丑数；
- 所以，从1开始，将每个丑数分别乘以2、3、5，然后取一个最小的作为下一个丑数：
- 为了让每个丑数都能和2、3、5相乘一次得到丑数，所以就得让得到最小丑数的那个数下次乘的丑数变成下一个，也就是让2、3、5不仅要和每个丑数相乘，而且和每个丑数只能相乘一次；
- 所以如果让三个下标i_2、i_3、i_5分别指向下一个要和2、3、5相乘的丑数的话，假如新得到的丑数是由乘2得到，则i_2++，其他两个不用加。
代码如下：
class Solution {
public:
int GetUglyNumber_Solution(int index) {
vector<int> u_nums(1, 1);
int i_2 = 0, i_3 = 0, i_5 = 0;
while (u_nums.size() <= index) {
int u_2 = u_nums[i_2] * 2;
int u_3 = u_nums[i_3] * 3;
int u_5 = u_nums[i_5] * 5;
int min_u = min(min(u_2, u_3), u_5);
if (min_u == u_2)
++i_2;
if (min_u == u_3)
++i_3;
if (min_u == u_5)
++i_5;
u_nums.push_back(min_u);
}
return u_nums[index-1];
}
};
