264. Ugly Number II
Write a program to find the n
-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5
. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12
is the sequence of the first 10
ugly numbers.
Note that 1
is typically treated as an ugly number, and n does not exceed 1690.
方法
由于丑数都可被2或3或5整除,所以可以使用3个变量分别存放大于当前result[i]的是2,3,5的倍数的数,然后可得:result[i] = Math.min(t2,Math.min(t3,t5))
,同时分别给t2,t3,t5三个指针,指出其大于result[i]的最小位置,然后根据最小位置的数求的新的t2,t3,t5.
public class Solution {
public int nthUglyNumber(int n) {
int[] result = new int[n];
int c2 = 0;
int c3 = 0;
int c5 = 0;
int t2 = 2;
int t3 = 3;
int t5 = 5;
result[0] = 1;
for(int i = 1; i < n; i++){
result[i] = Math.min(t2,Math.min(t3,t5));
while(t2 <= result[i]){
t2 = result[++c2] * 2;
}
while(t3 <= result[i]){
t3 = result[++c3] * 3;
}
while(t5 <= result[i]){
t5 = result[++c5]* 5;
}
}
return result[n-1];
}
}