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

# 丑数

## 题目 [丑数](https://www.acwing.com/problem/content/58/)

![[image-c864c33d.png]]

## 思路分析

将生成丑数的过程看作是从三个序列中选取最小值进行合并的过程，这三个序列分别是：

1. 由已知丑数乘以2得到的序列。
2. 由已知丑数乘以3得到的序列。
3. 由已知丑数乘以5得到的序列。

这样做的原因是任何一个丑数都可以通过前一个丑数乘以2、3或5得到。我们从1开始（1被视作第一个丑数），然后通过乘以2、3、5生成后续的丑数，并保持这些丑数是有序的。

1. 初始化三个指针`index2`、`index3`、`index5`，分别代表三个序列即将乘以2、3、5的丑数的位置，开始时都指向第一个丑数。
2. 每次计算三个序列`index2 * 2`、`index3 * 3`、`index5 * 5`的值，选择最小的那个作为新的丑数，加入到丑数序列中。
3. 如果选中的是哪个序列的值，则将该序列对应的指针加1。这表示我们用这个序列当前的丑数已经生成了下一个丑数，需要移动到下一个丑数继续进行生成。
4. 重复步骤2、3，直到找到第n个丑数为止。

这样，每次我们都从三个选项中选出最小的那个，保证了丑数的顺序。同时，每个丑数都是由前面的某个丑数通过乘以2、3或5得到的，确保了这确实是一个丑数。

![[image-162dd0c0.png]]

## 代码实现

```java
class Solution {

public:

    int getUglyNumber(int n) {

        if(n<=0)

            return 0;

        vector<int> ugly(n); // 存储丑数的数组

        ugly[0]=1;// 第一个丑数是1

        int nextidx=1;// 下一个丑数的索引

        int *pMultiply2=&ugly[0];// 指向数组的指针，初始时都指向第一个丑数

        int *pMultiply3=&ugly[0];

        int *pMultiply5=&ugly[0];

        while(nextidx<n){

            //从三个数组中找出最小的丑数加入

            int minval=min({*pMultiply2*2,*pMultiply3*3,*pMultiply5*5});

            ugly[nextidx]=minval;

            //更新对应序列的指针

            while(*pMultiply2*2<=ugly[nextidx])

                ++pMultiply2;

            while(*pMultiply3*3<=ugly[nextidx])

                ++pMultiply3;

            while(*pMultiply5*5<=ugly[nextidx])

                ++pMultiply5;

            ++nextidx;

        }

        return ugly[n-1];

    }

};
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/堆用法与模型/模拟堆|模拟堆]] 🏠 [[00-刷题理模型]] ➡️ [[世界首富|世界首富]]