49.丑数

raylan.chen大约 1 分钟

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/chou-shu-lcof/solutions/712103/chou-shu-by-leetcode-solution-0e5i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

使用一个最大堆来存储丑数，刚开始放入 1

随后，每次从最大堆中取出最小数，来和质因子 [2, 3, 5] 相乘，将相乘的乘积放入最大堆中排序（质因数 × 质因数 = 质因数）

另外，为了去重，在放入最大堆时，需要使用 Set 来防止重复元素的放入

每次从最大堆中取最小的丑数，直到循环 n 次退出

时间复杂度：O(n log(n))，循环 n 次，每次弹出元素 O(log(3n))，放入元素 O(3 log(3n))

49.丑数

49.丑数

参考链接

优秀题解