1. 代码段小站首页
  2. 算法

leetcode313-超级丑数

彭晨涛 • • 算法 • 阅读 10

原题

编写一段程序来查找第 n 个超级丑数。

超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

示例:

输入： n = 12, primes = [2,7,13,19] 输出： 32
解释： 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

说明：

  • 1 是任何给定 primes 的超级丑数。
  • 给定 primes 中的数字以升序排列。
  • 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
  • 第 n 个超级丑数确保在 32 位有符整数范围内。

解法

思想

该题和leetcode264-丑数II类似，可以使用堆来求解。

代码

class Solution {
    public int nthUglyNumber(int n) {
        Queue<Long> queue = new PriorityQueue<>();
        int count = 1;
        long cur = 1;
        while(count<n){
            queue.offer(cur*2);
            queue.offer(cur*3);
            queue.offer(cur*5);
            cur = queue.poll();
            while (!queue.isEmpty() && cur==queue.peek())
                queue.poll();
            count++;
        }
        return (int)cur;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode313-%e8%b6%85%e7%ba%a7%e4%b8%91%e6%95%b0/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年2月10日 23:55
下一篇 2020年2月11日 02:46

相关推荐

  • leetcode82-删除排序链表中的重复元素II

    原题 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示...

    彭晨涛 彭晨涛
    算法 2020年5月31日
    0190

  • leetcode25-K个一组翻转链表

    原题 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原...

    彭晨涛 彭晨涛
    算法 2020年5月9日
    0500

  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入：n = 3 输出：[ "((()))", "(()())", "...

    彭晨涛 彭晨涛
    算法 2020年4月9日
    060

  • 海量数据算法-BitMap介绍和实现

    作为一个有素质的程序员，在面试中（不是） 难免会遇到海量数据相关的问题，之前有注意过java.util下面有一个BitSet数据结构，但不是很明白是做什么用的。今天就来研究一下它背...

    彭晨涛 彭晨涛
    算法 2020年2月27日
    03280

  • 剑指offer44-数字序列中某一位的数字

    原题（来源Leetcode） 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位...

    彭晨涛 彭晨涛
    算法 2020年6月15日
    02570

  • leetcode1111-有效括号的嵌套深度

    原题 有效括号字符串 仅由 "(" 和 ")" 构成，并符合下述几个条件之一： 空字符串 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串 嵌套，可以...

    彭晨涛 彭晨涛
    算法 2020年4月1日
    070

  • leetcode12-整数转罗马数字

    原题 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2...

    彭晨涛 彭晨涛
    算法 2020年2月29日
    060

  • 剑指offer51-数组中的逆序对

    原题（来源Leetcode） 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1: 输入： [7...

    彭晨涛 彭晨涛
    算法 2020年4月24日
    0310

  • leetcode264-丑数II

    原题 编写一个程序，找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入： n = 10 输出： 12 解释： 1, 2, 3, 4, 5, 6, ...

    彭晨涛 彭晨涛
    算法 2020年2月10日
    0140
  • leetcode84-柱状图中最大的矩形 算法

    leetcode84-柱状图中最大的矩形

    原题 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 以上是柱状图的示例，其中每个柱子的宽...

    彭晨涛 彭晨涛
    2020年1月24日
    080

发表回复

登录后才能评论