类似264. Ugly Number II | Cinte's Leetcode Record
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> point(primes.size(), 0);
int m = primes.size();
vector<int> ret(n);
ret[0] = 1;
for(int i = 1; i < n; ++i)
{
int minVal = INT_MAX;
for(int j = 0; j < m; ++j)
{
minVal = min(ret[point[j]] * primes[j], minVal);
}
for(int j = 0; j < m; ++j)
if(minVal == ret[point[j]] * primes[j])
++point[j];
ret[i] = minVal;
}
return ret.back();
}
};
|
减少一次计算，用一个数组保存，将当前计算移动到上一轮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int m = primes.size();
vector<long> nums(n + 1);
vector<int> pt(m);
vector<long> tmp(m, 1);
for(int i = 1; i <= n; ++i)
{
long minNum = INT_MAX;
for(int j = 0; j < m; ++j)
minNum = min(tmp[j], minNum);
nums[i] = minNum;
for(int j = 0; j < m; ++j)
if(minNum == tmp[j])
tmp[j] = nums[++pt[j]] * primes[j];
}
return nums.back();
}
};
|