leetcode264-丑数II

原题

编写一个程序,找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5正整数

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

  1. 1 是丑数。
  2. n 不超过1690。

解法

思想

该题的关键是要知道丑数的顺序,从第一个丑数开始,得到它的2、3、5的倍数插入到最小堆中,这样每次我们从堆顶拿出来的都是堆中最小的元素,即下一个丑数,重复该步骤并计数就能得到目标解。

代码

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/leetcode264-%e4%b8%91%e6%95%b0ii/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月10日
下一篇 2020年2月11日

相关推荐

  • leetcode733-图像渲染

    原题 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一…

    2019年12月13日
    0100
  • leetcode1115-交替打印FooBar

    原题 我们提供一个类: class FooBar { public void foo() {     for (int i = 0; i < n; i++) {       …

    算法 2020年2月2日
    0170
  • 'leetcode50-Pow(x,n)'

    原题 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例1: 输入: 2.00000, 10 输出: 1024.00000 示例2: 输入: 2.10000, 3 输…

    算法 2020年1月5日
    0160
  • leetcode435-无重叠区间

    原题 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没…

    算法 2020年2月18日
    02420
  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

    算法 2020年5月4日
    080
  • leetcode557-反转字符串中的单词III

    原题 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例1: 输入: “Let’s take LeetCode contest” 输出: …

    算法 2019年11月23日
    0120
  • leetcode841-钥匙和房间

    原题 有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上,对于每个房间 i 都有一…

    2019年12月13日
    0120
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0130
  • leetcode380-常数时间插入、删除和获取随机元素

    原题 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 v…

    2019年12月28日
    0100
  • leetcode62-不同路径

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月21日
    0350

发表回复

登录后才能评论