网站开发视频播放好做吗,网页设计实训报告范文免费,wpautop wordpress,机关网站建设总结我们把只包含质因子 2、3 和 5 的数称作丑数#xff08;Ugly Number#xff09;。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明:
1 是丑数。n 不超过1690。
解题思路
使用小根堆#xf…我们把只包含质因子 2、3 和 5 的数称作丑数Ugly Number。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明:
1 是丑数。n 不超过1690。
解题思路
使用小根堆每次从小根堆拿出一个元素cur并且将cur *2cur *3,cur *5加入小根堆当第n次从小根堆出队的元素就是第n个丑数
代码
class Solution {public int nthUglyNumber(int n) {PriorityQueueLong priorityQueuenew PriorityQueue();HashSetLong hashSetnew HashSet();priorityQueue.add(1L);hashSet.add(1L);for (int i0;in-1;i){long cur priorityQueue.poll();if (!hashSet.contains(cur*2)){hashSet.add(cur*2);priorityQueue.add(cur*2);}if (!hashSet.contains(cur*3)){hashSet.add(cur*3);priorityQueue.add(cur*3);}if (!hashSet.contains(cur*5)){hashSet.add(cur*5);priorityQueue.add(cur*5);}}return (int)priorityQueue.poll().longValue();}
}
