設(shè)計一個算法，找出只含素因子2建蹄，3陋气，5 的第 n 小的數(shù)。
符合條件的數(shù)如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
樣例
樣例 1：
輸入：9
輸出：10
樣例 2：
輸入：1
輸出：1
分析：假設(shè)數(shù)組ugly[N]中存放不斷產(chǎn)生的丑數(shù)懒闷，初始只有一個丑數(shù)ugly[0]=1，由此出發(fā)栈幸，下一個丑數(shù)由因子2,3,5競爭產(chǎn)生愤估，得到ugly[0]*2, ugly[0]*3, ugly[0]*5， 顯然最小的那個數(shù)是新的丑數(shù)速址，所以第2個丑數(shù)為ugly[1]=2玩焰，開始新一輪的競爭，由于上一輪競爭中芍锚，因子2獲勝昔园，這時因子2應(yīng)該乘以ugly[1]才顯得公平，得到ugly[1]*2,ugly[0]*3,ugly[0]*5闹炉， 因子3獲勝，ugly[2]=3润樱，同理渣触，下次競爭時因子3應(yīng)該乘以ugly[1]，即：ugly[1]*2, ugly[1]*3, ugly[0]*5, 因子5獲勝壹若，得到ugly[3]=5嗅钻，重復(fù)這個過程，直到第n個丑數(shù)產(chǎn)生店展⊙ǎ總之：每次競爭中有一個（也可能是兩個或三個）因子勝出，下一次競爭中 勝出的因子就應(yīng)該乘下一個數(shù)赂蕴。
public class Solution {
/**
* @param n: An integer
* @return: return a integer as description.
*/
public int nthUglyNumber(int n) {
// write your code here
int i = 0;
int j = 0;
int k = 0;
int index = 1;
int[] dp = new int[n];
dp[0] = 1;
while (index < n) {
dp[index] = Math.min(Math.min(dp[i] * 2, dp[j] * 3), dp[k] * 5);
if (dp[index] == dp[i] * 2) {
i++;
}
if (dp[index] == dp[j] * 3) {
j++;
}
if (dp[index] == dp[k] * 5) {
k++;
}
index++;
}
return dp[n - 1];
}
}
Github 地址： https://github.com/xingfu0809/Java-LintCode
