php网站留言板模板,浙江新地标建设集团网站,公司用dw做网站吗,彩票黑网站是怎么做的给你一个整数 n #xff0c;请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1#xff1a;
输入#xff1a;n 10 输出#xff1a;12 解释#xff1a;[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
解题思路
维…给你一个整数 n 请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1
输入n 10 输出12 解释[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
解题思路
维护一个最小堆和一个set记录以及进入堆的丑数每次将堆的最小值出队并且将它的235倍数入队
代码
class Solution {public int nthUglyNumber(int n) {PriorityQueueLong priorityQueuenew PriorityQueue();SetLong setnew HashSet();priorityQueue.add(1L);int cnt0;while (true){long curpriorityQueue.poll();cnt;if(cntn)return (int)cur;if(!set.contains(cur*2)){priorityQueue.add(cur*2); set.add(cur*2);}if(!set.contains(cur*3)){priorityQueue.add(cur*3);set.add(cur*3);}if(!set.contains(cur*5)){priorityQueue.add(cur*5);set.add(cur*5);}}}
}
