264. Ugly Number II

问题

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

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

例子

10
12

分析

dp. 开辟一个n大小的状态表，第一个元素初始化为1。每次生成第i个丑数时，从0到i-1遍历状态表，将元素分别乘2, 3, 5，当乘积大于第i-1个丑数时终止循环。则第i个丑数为循环结束前的元素乘2, 3, 5的乘积中最小的那个。

优化：不用每次都从0开始遍历，用p2, p3, p5分别保存上次乘2, 3, 5的乘积大于第i-1个丑数的第一个元素的下标。下次直接从p2, p3, p5遍历就可以了。

要点

dp

时间复杂度

O(n)

空间复杂度

O(n)

代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> v(n); v[0] = 1;
        int factor[3] = { 2, 3, 5 };
        int p2 = 0, p3 = 0, p5 = 0;
        int m2 = 0, m3 = 0, m5 = 0;
        for (int i = 1; i < n; i++) {
            while (v[p2] * 2 <= v[i - 1]) p2++;
            m2 = v[p2] * 2;
            
            while (v[p3] * 3 <= v[i - 1]) p3++;
            m3 = v[p3] * 3;
            
            while (v[p5] * 5 <= v[i - 1]) p5++;
            m5 = v[p5] * 5;
            
            v[i] = min(m2, min(m3, m5));
        }
        return v.back();
    }
};