java如何查出丑数
本文将为大家详细介绍“java如何查出丑数”，内容步骤清晰详细，细节处理妥当，而小编每天都会更新不同的知识点，希望这篇“java如何查出丑数”能够给你意想不到的收获，请大家跟着小编的思路慢慢深入，具体内容如下，一起去收获新知识吧。
成都创新互联公司主打移动网站、成都网站建设、做网站、网站改版、网络推广、网站维护、域名与空间、等互联网信息服务，为各行业提供服务。在技术实力的保障下，我们为客户承诺稳定，放心的服务，根据网站的内容与功能再决定采用什么样的设计。最后，要实现符合网站需求的内容、功能与设计，我们还会规划稳定安全的技术方案做保障。
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10 输出: 12 解释: 是前 10 个丑数。
说明:
1是丑数。n不超过1690。
答案：
1public int nthUglyNumber(int n) {
2 if (n <= 1)
3 return n;
4 int t2 = 0, t3 = 0, t5 = 0;
5 int[] k = new int[n];
6 k[0] = 1;
7 for (int i = 1; i < n; i++) {
8 k[i] = Math.min(k[t2] * 2, Math.min(k[t3] * 3, k[t5] * 5));
9 if (k[i] == k[t2] * 2)
10 t2++;
11 if (k[i] == k[t3] * 3)
12 t3++;
13 if (k[i] == k[t5] * 5)
14 t5++;
15 }
16 return k[n - 1];
17}
解析：
丑数除了第一个是0以外，其他的都可以这样表示
1*（2，3，5），
2*（2，3，5），
3*（2，3，5），
4*（2，3，5），
……………………
题目中说要找到第n个丑数，这n个丑数都是按照从小到大的顺序查找的。所以每次查找的时候都是找最小的。下面再来看一种解法
1public int nthUglyNumber(int n) {
2 if (n == 1)
3 return 1;
4 PriorityQueue q = new PriorityQueue();
5 q.add(1L);
6 for (long i = 1; i < n; i++) {
7 long tmp = q.poll();
8 while (!q.isEmpty() && q.peek() == tmp)
9 tmp = q.poll();
10 q.add(tmp * 2);
11 q.add(tmp * 3);
12 q.add(tmp * 5);
13 }
14 return q.poll().intValue();
15}
PriorityQueue默认是一个小顶堆的优先队列，poll表示的是移除最顶端的元素，也是最小的元素，然后再用最小的元素分别和2,3,5进行相乘，add方法加入到队列的时候又会进行排序，保证最顶端的元素是最小的。
Java可以用来干什么
Java主要应用于：1. web开发；2. Android开发；3. 客户端开发；4. 网页开发；5. 企业级应用开发；6. Java大数据开发；7.游戏开发等。
感谢您能读到这里，小编希望您对“java如何查出丑数”这一关键问题有了从实践层面最深刻的体会，具体使用情况还需要大家自己动手实践使用过才能领会，如果想阅读更多相关内容的文章，欢迎关注创新互联行业资讯频道！
网页名称：java如何查出丑数
浏览路径：http://azwzsj.com/article/pjsgej.html
