Leetcode 264. 丑数 II(最小堆)

2022-09-11 22:22 34阅读 0赞

## 题目重述 ##

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

### 示例 1： ###

输入：n = 10
    输出：12
    解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

### 示例 2： ###

输入：n = 1
    输出：1
    解释：1 通常被视为丑数。

### 提示： ###

1 <= n <= 1690

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ugly-number-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

*  使用最小堆，预先放1，后续弹出x的时候，add上2x,3x,5x，因为他们都是丑数
 *  需要注意的是弹出的可能出现重复的现象，可以用哈希判断一下

## Java实现 ##

class Solution {
        
        public int nthUglyNumber(int n) {
        
            if (n == 1) {
        
                return 1;
            }
            Map<Long, Integer> m = new HashMap<>();
            PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
            priorityQueue.add(1l);
            Long  t = 0l;
            while (n > 0) {
        
                t = priorityQueue.poll();
                // 已经出去过的话 需要再出去一下
                while (m.containsKey(t)) {
        
                    t = priorityQueue.poll();
                }
                // 标志已经出去过了
                m.put(t, 0);
                n--;
                // add新的
                priorityQueue.add(t * 2);
                priorityQueue.add(t * 3);
                priorityQueue.add(t * 5);
            }
            return t.intValue();
        }
    }

文章版权声明：注明蒲公英云原创文章，转载或复制请以超链接形式并注明出处。

发表评论取消回复

表情：

评论列表（有 0 条评论，34人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 264 丑数II

我的算法水平算是很差的那种。。这道题一开始自己想得办法一直都是超时，看了大牛们的思路之后，恍然大悟在此做一个总结 1.题目名称 Ugly Number II (丑数2：返

快来打我*/ 2022年02月28日 20:38/ 0 赞/ 73 阅读

相关 LeetCode——丑数

题目：编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 `2, 3, 5` 的正整数。示例 1: 输入: 6 输出: true 解

╰+哭是因爲堅強的太久メ/ 2022年03月27日 21:42/ 0 赞/ 89 阅读

相关【LeetCode】263. 丑数

题目链接：[https://leetcode-cn.com/problems/ugly-number/description/][https_leetcode-cn.com_p

骑猪看日落/ 2022年04月22日 07:26/ 0 赞/ 38 阅读

相关【LeetCode】264. 丑数 II

题目链接：[https://leetcode-cn.com/problems/ugly-number-ii/description/][https_leetcode-cn.co

小鱼儿/ 2022年04月22日 07:26/ 0 赞/ 40 阅读

相关 leetcode 264. Ugly Number II

Write a program to find the `n`\-th ugly number. Ugly numbers are positive numbers whos

超、凢脫俗/ 2022年07月26日 08:15/ 0 赞/ 21 阅读

相关 leetcode263丑数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

矫情吗；*/ 2022年09月04日 08:41/ 0 赞/ 15 阅读

相关 Leetcode 264. 丑数 II(最小堆)

题目重述给你一个整数 n ，请你找出并返回第 n 个丑数。丑数就是只包含质因数 2、3 和/或 5 的正整数。示例 1：输入：n = 10

怼烎@/ 2022年09月11日 22:22/ 0 赞/ 35 阅读

相关 LeetCode 264. 丑数 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

缺乏、安全感/ 2022年10月28日 18:13/ 0 赞/ 25 阅读

相关 LeetCode264. 丑数 II

难度：`中等` 题目描述： > 给你一个整数 n ，请你找出并返回第 n 个丑数。 > 丑数就是只包含质因数 2、3 和/或 5 的正整数。示例 1： >

小鱼儿/ 2022年11月18日 09:43/ 0 赞/ 27 阅读

相关 leetcode264丑数

丑数就是质因数只包含 2, 3, 5 的正整数输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10

朱雀/ 2023年03月14日 21:20/ 0 赞/ 69 阅读