丑数II

题意

设计一个算法,找出只含素因子235 的第 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。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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);
}
};

原题地址

LintCode:丑数II

坚持原创技术分享,您的支持将鼓励我继续创作!