LeetCode——264.丑数II（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 通常被视为丑数。


题解分析

输出第n个丑数，首先我们要知道丑数的定义，定义就是题干说的那样，我们一般把1当作第一个丑数，依次往后排
当然思路很清晰就是生成丑数数组，最后返回第n个即可，但是怎么生成丑数的顺序数组呢
这里采用了Queue的一个实现类PriorityQueue，也就是一个最小堆模型，这样保证每次得到最小的元素
我们发现丑数肯定是2，3或者5的倍数，所以我们只要按照这个规律插入元素然后用PriorityQueue返回第n个即可


正确代码

public int nthUglyNumber(int n){
int[] factors = {2,3,5};
PriorityQueue heap = new PriorityQueue<>();
Set set = new HashSet();
set.add(1L);
heap.offer(1L);
int ugly = 0;
for (int i = 0; i long curr = heap.poll();
ugly = (int)curr;
//添加2、3或者5的倍数
for (int factor : factors) {
long next = curr * factor;
//排除重复元素
if (set.add(next)){
heap.offer(next);
}
}
}
return ugly;
}


总结

这里使用了一个PriorityQueue实现类，这个类是模仿了最小堆的结构，保证了每次返回的元素都是堆中的最小值
如果用数组保存的话虽然可以查看其它元素，但是当然也会添加额外的空间消耗，当然官网也有动态规划方法，效率也是比这个高的
当然每次这种题目，总会有大佬采用面向结果编程，直接把答案数组返回，这肯定是不能超越的速度
如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，你我最高处见