设计一个算法,找出只含素因子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);
}
};