题目
描述
设计一个算法，找出只含素因子2，3，5 的第 n 大的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
样例
如果n = 9， 返回 10
解答
思路
任何丑数都可以表示为：i^2 * j^3 * k^5；后一个丑数等于前面某个丑数乘以2或3或5：
- 定义一个大小为n的数组u[n]用来存储有序丑数序列。
- 三个游标
u2,u3,u5分别表示乘以2或3或5取得过最新丑数。 - 下一个丑数等于
min(u[u2]*2, u[u3]*3, u[u5]*5)，并根据因子对u2或u3或u5递增。
代码
代码语言：javascript复制class Solution {
/**
* @param n an integer
* @return the nth prime number as description.
*/
public int nthUglyNumber(int n) {
// Write your code here
int[] u = new int[n];
u[0] = 1;
int u2 = 0,u3 = 0, u5 = 0;
for(int i = 1; i < n; i ){
u[i] = min(min(u[u2]*2,u[u3]*3),u[u5]*5);
if((u[i]/u[u2]) == 2) u2 ;
if((u[i]/u[u3]) == 3) u3 ;
if((u[i]/u[u5]) == 5) u5 ;
}
return u[n-1];
}
public int min(int a, int b){
return a < b ? a : b;
}
};
