LeetCode-264：丑数 II
一、题目描述
二、解题思路
采用三指针法
丑数是因数只有2, 3, 5的数字，设置一个dp数组表示当前已经找到的有序丑数。那么这个序列分别乘以2, 3, 5之后得到的序列肯定还是丑数序列
首先第一个数字肯定是1，第二个也不难推出是2
但是怎么确定先后顺序：1得到2, 3, 5，2得到4, 6, 10。如果直接接在后面，可以看到不成顺序，违背了dp是已经找到的有序丑数这一设定，导致后面的工作无法进行。
2该乘谁？3该乘谁？4该乘谁？
我们可以设定三个指针，分别指向该乘2、乘3和乘5的位置，这里具体意义为数组下标。把它们都赋初值为0。
于是第一轮我们可以从dp序列里得到从1推倒出来的待选序列：2, 3, 5，选择一个最小的加入进去，这里选择了2。此时dp数组变为[1, 2]。由于2已经加入，再比较无意义，于是将指向乘2位置的指针指向下一位置，即指向dp = [1, 2]中的第二个位置。
第二次循环，乘2指针指向dp[1]，得到cmp2 = 4；乘3指针指向dp[0]，得到cmp2 = 3；乘5指针指向dp[0]，得到cmp2 = 5.选择一个最小的结果（即为cmp2 = 3）插入数组，得到dp = [1, 2, 3]
再来说说需要注意的情况：如果cmp2 == cmp3或者cmp2 == cmp5或者cmp3 == cmp5的情况发生，以cmp3 == cmp5为例，那么说明cmp3 == cmp5这个数字已经被加入到了dp中，如果不同时把两个指针更新，那么必然在下次计算时该值被重新参与比较，这是无意义的，所以应该在这种情况下也把指针后移一步，具体到代码里就是
if(MIN == cmp2) ptr2++;
if(MIN == cmp3) ptr3++;
if(MIN == cmp5) ptr5++;
而不是
if(MIN == cmp2) ptr2++;
else if(MIN == cmp3) ptr3++;
else ptr5++;
三、解题代码
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n, 1);
int ptr2 = 0, ptr3 = 0, ptr5 = 0;
for(int i = 1; i < n; i++){
int cmp2 = dp[ptr2] * 2, cmp3 = dp[ptr3] * 3, cmp5 = dp[ptr5] * 5;
auto MIN = min(cmp2, min(cmp3, cmp5));
if(MIN == cmp2) ptr2++;
if(MIN == cmp3) ptr3++;
if(MIN == cmp5) ptr5++;
dp[i] = MIN;
}
return dp.back();
}
};
