264. Ugly Number II

problem description

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number. n does not exceed 1690.

algorithm thought

这是ugly number的第二题，这个系列有4题。和第一题直接判断是否为ugly number不同。这里需要求出第几个ugly number。最简单暴力的办法当然是直接循环遍历，符合要求就加一。否则一直往后求。但是这样太慢了。有很多重复操作。之前计算过了4是一个ugly number，在求解8是否为ugly number的时候，还要去求4的情况。这就会有重复计算。

由于ugly number是可以由前面的uglynumebr得到。利用类似步长调用的方法。3个步长分别为2，3，5。每次步长最低的人行动。直到第n个数

code

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n<=1)
            return 1;
        vector<int> res(n,1);
        int t1=0,t2=0,t3=0;
        for(int i=1;i<n;++i){
            res[i]=min(res[t1]*2,min(res[t2]*3,res[t3]*5));
            if(res[t1]*2==res[i])
                t1++;
            if(res[t2]*3==res[i])
                t2++;
            if(res[t3]*5==res[i])
                t3++;
        }
        return res.back();
    }
};

algorithm analysis

每得到一个数时间复杂度是O(1)，题目要求得到第n个数。时间复杂度O(n)