题解 | #丑数#_牛客博客

题目的主要信息：

把只包含质因子2、3和5的数称作丑数
求按从小到大的顺序的第n个丑数
1视作第一个丑数

方法一：最小堆（推荐使用）

知识点1：优先队列

优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是 $O (l o g_{2} n)$ ，而每次取出堆顶元素都是直接取出。

知识点2：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在 $O (1)$ 时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

我们都知道如果 $x$ 是丑数，则 $2 x$ 、 $3 x$ 、 $5 x$ 都是丑数，丑数也是从1开始由每个丑数这样构建而来的，我们要做的就是找到这样的前 $n$ 个数，即最小的 $n$ 个。

整体排序不现实，但是我们可以利用小顶堆，即优先队列，每次取出堆顶元素一定是最小的，一共取 $n$ 次就可以了，每次取出来的元素我们分别乘2、乘3、乘5后入堆，即作为之后要访问的数字，当然为了防止重复比如 $2 * 3 = 6$ 、 $3 * 2 = 6$ ，我们还要用哈希表去重。

这里面有的数字会超过int的表示范围，因此哈希表和小顶堆都用long。

具体做法：

step 1：使用小顶堆记录即将从小到大访问的丑数，哈希表去重，数组记录2、3、5乘数因子。
step 2：数字1作为第一个丑数，首先入堆，后面的丑数都是其不断乘上2、3、5的结果。
step 3：每次依次从小顶堆中弹出最小的元素，一共弹出n次。
step 4：对于每个弹出的元素，可以用起构造后面的丑数，即分别乘上2、3、5，若是不重复则加入堆中排队等到访问。

Java实现代码：

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0; 
        //要乘的因数
        int[] factors = {2, 3, 5}; 
        //去重
        HashMap<Long, Integer> mp = new HashMap<>();
        //小顶堆
        PriorityQueue<Long> pq = new PriorityQueue<>(); 
        //1先进去
        mp.put(1L, 1);
        pq.offer(1L);
        long res = 0;
        for(int i = 0; i < index; i++){ 
            //每次取最小的
            res = pq.poll(); 
            for(int j = 0; j < 3; j++){
                //乘上因数
                long next = (long)res * factors[j]; 
                //只取未出现过的
                if(!mp.containsKey(next)){  
                    mp.put(next, 1);
                    pq.offer(next);
                }
            }
        }
        return (int)res;
    }
}

C++实现代码：

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0; 
        //要乘的因数
        vector<int> factors = {2, 3, 5}; 
        //去重
        unordered_map<long, int> mp; 
        //小顶堆
        priority_queue<long, vector<long>, greater<long>> pq; 
        //1先进去
        mp[1LL] = 1; 
        pq.push(1LL);
        long res = 0;
        for(int i = 0; i < index; i++){ 
            //每次取最小的
            res = pq.top(); 
            pq.pop();
            for(int j = 0; j < 3; j++){
                //乘上因数
                long next = res * factors[j]; 
                //只取未出现过的
                if(mp.find(next) == mp.end()){  
                    mp[next] = 1;
                    pq.push(next);
                }
            }
        }
        return (int)res;
    }
};

Python实现代码：

class Solution:
    def GetUglyNumber_Solution(self , index: int) -> int:
        #排除0
        if index == 0:
            return 0
        #要乘的因数
        factors = [2, 3, 5]
        #去重
        mp = dict()
        #小顶堆
        import heapq
        pq = []  
        #1先进去
        mp[1] = 1 
        heapq.heappush(pq, 1)
        res = 0
        for i in range(index):
            #每次取最小的
            res = pq[0] 
            heapq.heappop(pq)
            for j in range(3):
                #乘上因数
                next = res * factors[j]
                #只取未出现过的
                if next not in mp:
                    mp[next] = 1
                    heapq.heappush(pq, next)
        return res

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，一共循环 $n$ 次，取 $n$ 次最小值，每次循环中最多有3次入堆操作，每次入堆都是 $O (l o g_{2} n)$ ，哈希表的操作是 $O (1)$
空间复杂度： $O (n)$ ，哈希表和小顶堆最大空间为 $3 * n$ 的长度

方法二：动态规划（扩展思路）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。