---
title: "超级丑数"
created: 2025-11-28
tags:
  - 算法
---

# 超级丑数

## 题目 [超级丑数](https://leetcode.cn/problems/super-ugly-number/)

![[image-32173a2d.png]]

## 思路分析

![[image-459cedb4.png]]

区别是指针数量变为`k`个, 即起始时`k`个指针一起指向丑数数组`0`位置

涉及两部分修改:

- 找到`k`个指针指向的最小值`minVal`作为当前加入`ugly`的元素(要简化`LC264`中找最小值的一步f)
- 修改所有指向`minVal`的指针(`p++`)

以上两个操作适合用`priority_queue`来实现

另外要注意`PII`的第一维需要用`long long`类型

## 代码实现

```java
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();

    }

};
```

## 同类题型

## 视频讲解

---
⬅️ [[谦虚数字|谦虚数字]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/多路归并相关问题/鱼塘钓鱼|鱼塘钓鱼]]