問題
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大小的狀態(tài)表，第一個元素初始化為1驶沼。每次生成第i個丑數(shù)時澎羞，從0到i-1遍歷狀態(tài)表盒至，將元素分別乘2, 3, 5膳汪，當乘積大于第i-1個丑數(shù)時終止循環(huán)。則第i個丑數(shù)為循環(huán)結(jié)束前的元素乘2, 3, 5的乘積中最小的那個滓鸠。
優(yōu)化：不用每次都從0開始遍歷卦绣，用p2, p3, p5分別保存上次乘2, 3, 5的乘積大于第i-1個丑數(shù)的第一個元素的下標。下次直接從p2, p3, p5遍歷就可以了盒延。
要點
dp
時間復(fù)雜度
O(n)
空間復(fù)雜度
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();
}
};
