超级丑数
题目 超级丑数
思路分析
区别是指针数量变为k个, 即起始时k个指针一起指向丑数数组0位置
涉及两部分修改:
- 找到
k个指针指向的最小值minVal作为当前加入ugly的元素(要简化LC264中找最小值的一步f) - 修改所有指向
minVal的指针(p++)
以上两个操作适合用priority_queue来实现
另外要注意PII的第一维需要用long long类型
代码实现
class Solution {
public:
typedef pair<long long, int> PII;
int nthSuperUglyNumber(int k, vector<int>& primes) {
vector<int> ugly;
ugly.push_back(1);
// PII第一维存储「下一个要加入的元素(每个数组的头部)」, 第二维存储「数组当前下标」(指针)
priority_queue<PII, vector<PII>, greater<PII>> pq;
for(int i=0; i<primes.size(); i++){
pq.push({primes[i]*1, 0});//每种情况都乘一下 存进去 堆顶的是最小的
}
while(ugly.size() < k){
int minVal = pq.top().first;
ugly.push_back(minVal);
// 弹出所有重复minVal, 并移动指针
while(!pq.empty() && pq.top().first==minVal){
PII cur = pq.top();
int ptr = cur.second;
int prime = cur.first / ugly[ptr];
pq.pop();
pq.push({(long long)prime * (ugly[ptr+1]), ptr+1});
}
}
return ugly.back();
}
};
💬 评论