丑数II
题意
设计一个算法，找出只含素因子2，3，5 的第 n 大的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
注意事项：我们可以认为 1 也是一个丑数
样例
如果n = 9， 返回 10
思路
其实改题的题意就是在所有 丑数 列表中，找到第 n 个丑数。
最简单的做法是从 1 开始，判断每一个数是否是一个丑数，是的话则加到丑数列表中，直到丑数列表的大小等于 n，但是这种方法效率较低，我们可以根据规律而尝试只创造出有效的丑数。
1*2=2 2*2=4 3*2=6 4*2=8 5*2=10 ...
1*3=3 2*3=6 3*3=9 4*3=12 5*3=15 ...
1*5=5 2*5=10 3*5=15 4*5=20 5*5=25 ...观察规律可得，丑数是取已有的丑数乘以 2 或 3 或 5 得到的，那么我们可以先将特殊的丑数 1 放进丑数列表中。
因为已存在的丑数肯定在列表中是按照顺序存放的，所以对于乘以 2 而言，肯定存在一个丑数 p2，在它之前的每一个丑数乘以 2 都是当前列表中最后一个丑数的，通用，在它之后的每一个丑数乘以 2 的结果都是大于当前列表中最后一个丑数的，我们只需要记住 p2 的这个位置，同样存在的还有 p3 和 p5，记住这 3 个数的位置，就可以一些避免不必要的比较。
我们只需要取出 p2, p3, p5 位置的那个数，分别乘以 2, 3, 5 将结果最小的存入到丑数列表中即可。直到丑数列表的个数达到 n。
代码实现
public class Solution {
/*
* @param n: An integer
* @return: the nth prime number as description.
*/
public int nthUglyNumber(int n) {
if (n == 1) {
return 1;
}
List<Integer> uglys = new ArrayList<Integer>();
uglys.add(1);
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int lastUgly = uglys.get(i - 1);
while (uglys.get(p2) * 2 <= lastUgly) p2++;
while (uglys.get(p3) * 3 <= lastUgly) p3++;
while (uglys.get(p5) * 5 <= lastUgly) p5++;
uglys.add(Math.min(
Math.min(uglys.get(p2) * 2, uglys.get(p3) * 3),
uglys.get(p5) * 5)
);
}
return uglys.get(n -1);
}
};原题地址
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-08-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录