題目：把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）犀填。例如6萌京、8都是丑數(shù)，但14不是宏浩，因為它包含因子7知残。 習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。求按從小到大的順序的第N個丑數(shù)比庄。
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index < 7){
return index;
}
int[] res = new int[index];
res[0] = 1;
int t2 = 0, t3 = 0, t5 = 0;
for(int i = 1; i < index; i++){
res[i] = getMin(2 * res[t2], 3 * res[t3], 5 * res[t5]);
if(res[i] == 2 * res[t2]) t2++;
if(res[i] == 3 * res[t3]) t3++;
if(res[i] == 5 * res[t5]) t5++;
}
return res[index - 1];
}
int getMin(int i, int j, int k){
return i < j ? (i < k ? i : k) : (j < k ? j :k);
}
}
通過題目可以知道一個丑數(shù)是一個因子只有2求妹，3，5的數(shù)佳窑，題目要求我們求出第n個丑數(shù)制恍，我們可以通過從頭構(gòu)建的形式一步一個腳印的推到每一個丑數(shù)，這就需要一些技巧了神凑。
- 首先净神，我們用一個數(shù)組按從小到大的順序存儲獲得的丑數(shù)何吝，并初始化以第一個丑數(shù)
- 我們可以知道，一個丑數(shù)一定可以通過之前的某一個丑數(shù)?2or3or5來得到
- 所以我們定義了三個指針分別表述2鹃唯，3爱榕，5上次被用來獲取丑數(shù)的位置，也是用來維護(hù)下一次我能夠獲得的丑數(shù)的位置
（假設(shè)上一次通過2 * 丑數(shù)4獲得了一個丑數(shù)8坡慌，然后我們下一次再通過2來獲得丑數(shù)就是2* 丑數(shù)4之后的丑數(shù)了黔酥，也就是5，我們下一次可以通過2*5來獲得一個丑數(shù)） - 定一個了三個指針之后洪橘，開始真正的生成丑數(shù)跪者，通過比較用2，3熄求，5三個指針來獲取的丑數(shù)的大小渣玲，選取最小的結(jié)果做為下一個丑數(shù)，并將相應(yīng)的指針向后移動一位弟晚。
- 直到獲得了第n個指針柜蜈，return
