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.
Solution：
思路： 在ugly-sequence自己基礎(chǔ)上再 * 2, 3, 5產(chǎn)生新的秉氧。用index/progres數(shù)組記錄factor已經(jīng)在自己原數(shù)組上乘到的位置(已經(jīng)用過的)绍些，三個(gè)對(duì)應(yīng)位置取出最小的即横，更新位置蝙泼。
屏幕快照 2017-09-09 下午7.33.24.png
Time Complexity: O(N) Space Complexity: O(N)
Solution1_a Code：
public class Solution {
public int nthUglyNumber(int n) {
int[] ugly = new int[n];
ugly[0] = 1;
int index2 = 0, index3 = 0, index5 = 0;
int factor2 = 2, factor3 = 3, factor5 = 5;
for(int i=1;i<n;i++){
int min = Math.min(Math.min(factor2,factor3),factor5);
ugly[i] = min;
if(factor2 == min)
factor2 = 2*ugly[++index2];
if(factor3 == min)
factor3 = 3*ugly[++index3];
if(factor5 == min)
factor5 = 5*ugly[++index5];
}
return ugly[n-1];
}
}
Solution1_b Code：
class Solution {
public int nthUglyNumber(int n) {
int factors[] = new int[] {2, 3, 5};
int progres[] = new int[factors.length]; //for factors' own progress
int result[] = new int[n + 1];
result[0] = 1;
for(int i = 1; i <= n; i++) {
// get min value from factors.length of candidates
int g_min = Integer.MAX_VALUE;
for(int f = 0; f < factors.length; f++) {
int cur_min = factors[f] * result[progres[f]];
if(cur_min < g_min) g_min = cur_min;
}
// update those winning(include ties) candidates' progress
for(int f = 0; f < factors.length; f++) {
if(factors[f] * result[progres[f]] == g_min) progres[f]++;
}
result[i] = g_min;
}
return result[n - 1];
}
}
