Java中等题-丑数（力扣）

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

我的思路是用一个大根堆，但是会超时

下面是会超时的错误示范

class Solution {public int nthUglyNumber(int n) {if(n<=6){return n;}PriorityQueue tree=new PriorityQueue(new Comparator() {@Overridepublic int compare(Object o1, Object o2) {return 01-02;}});int i = bigTree(tree, n);return i;}public int bigTree(PriorityQueue tree,int n){int i=1;while(tree.size()<n){if(isChou(i)){tree.add(i);}i++;}return (int) tree.peek();}public boolean isChou(int i){int t=i;while((t/2)*2==i){i/=2;t=i;}while((t/3)*3==i){i/=3;t=i;}while((t/5)*5==i){i/=5;t=i;}if(i==1){return true;}return false;}
}

看看官方怎么做的：

class Solution {public int nthUglyNumber(int n) {int[] factors = {2, 3, 5};Set<Long> seen = new HashSet<Long>();PriorityQueue<Long> heap = new PriorityQueue<Long>();seen.add(1L);heap.offer(1L);int ugly = 0;for (int i = 0; i < n; i++) {long curr = heap.poll();ugly = (int) curr;for (int factor : factors) {long next = curr * factor;if (seen.add(next)) {heap.offer(next);}}}return ugly;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/ugly-number-ii/solutions/712102/chou-shu-ii-by-leetcode-solution-uoqd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

感觉思路都差不多呢，为什么官方的就不会超时，不是很理解，有没有懂得小伙伴说说