264. Ugly Number II

264. Ugly Number II

dp

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0] = 1;
        int l1 = 0, l2 = 0, l3 = 0;
        for(int i = 1; i < n; ++i)
        {
            auto t1 = dp[l1] * 2;
            auto t2 = dp[l2] * 3;
            auto t3 = dp[l3] * 5;
            dp[i] = min(min(t1, t2), t3);
            if(dp[i] == t1)
                ++l1;
            if(dp[i] == t2) // 去重，如果一个值在当前回合是最小值，那么如果存在重复，在下一回合中他也是最小值，因此需要去重。不能用else if
                ++l2;       // 不仅仅是去重，还需要指针的移动
            if(dp[i] == t3)
                ++l3;
        }
        return dp.back();
    }
};

维护三个序列，分别是x2，x3，x5的序列。其中通过l1,l2,l3表示

这三个序列通过指针的位置来表示，当这个序列的用完后，根据dp中由小到大排，那么移动到下一个作为下一个的候选

之所以可以这样是因为dp已经帮助我们实现排序，因此只需要应用之前的排序结果，取了其中一个序列的一个值后，把他移动到序列的下一个位置，也就是ugly number种刚好比他大的一个数。注意三个数的序列可能会发生重叠。因此需要去重处理。