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/

发表评论

电子邮件地址不会被公开。