原题
编写一个程序,找出第 n
个丑数。
丑数就是只包含质因数 2, 3, 5
的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1
是丑数。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/