【剑指 offer】丑数

1、题目描述

我们把只包含因子2、3和5的数称作丑数（Ugly Number）。

例如6、8都是丑数，但14不是，因为它包含因子7。

求第n个丑数的值。

样例：

输入：5
输出：5

注意：习惯上我们把1当做第一个丑数。

2、问题描述：

1, 2, 3, 4, 5, 6, 8, 9, 10 ...

3、问题关键：

• 可以看出下一个丑数是前面的某个数乘于（2， 3， 5）中的一个获得的最小值。
• 可以用三个指针，i，j，k，依次指向1，2，3 ...前面的数，乘于（2， 3， 5），穷举所有的丑数。

4、C++代码：

class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> q(1, 1);//定义一个可变数组，值为1。
        int i = 0, j = 0, k = 0;//同时指向第一个位置。
        while(-- n) {
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));//下一个数是，当前数组中乘于（2， 3， 5）得到的最小值。
            q.push_back(t);
            if (q[i] * 2 == t) i ++;//放入数组中，并将i向后移动一个位置。
            if (q[j] * 3 == t) j ++;
            if (q[k] * 5 == t) k ++;
        }
        return q.back();//最后一个就是第n个丑数。
        
    }
};