题目描述
- 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路
- 既然是只包含2/3/5通全城的丑数，那么这些数字必然是丑数乘以2/3/5上去的，我们可以声明一个数组result大小为index+1(保证下标和index对齐)，然后result[1]表示第一个丑数就是1。
- 然后我们需要根据已知丑数去求未知丑数，并且是有序的，那么规则就是只需要求得未出现的最小丑数即可
- 因为需要对每个丑数都进行乘以2乘以3和乘以5的操作，那么就可以设置三个索引变量，然后分别将当前索引对应的值乘以2乘以3和乘以5进行比较得到最小的即可
- 之后需要更新2/3/5对应的索引需要将其索引对应的值乘以相应的因子和当前已经加入到数组的数据进行比较，如果比这个数小那么需要一直更新到大于等于这个数，有点类似快排里面的查找过程
假设当前索引
更新后的索引
Java源代码
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index <= 0) return 0;
int[] result = new int[index+1];
result[0]=0;
result[1]=1;
int index2 = 1;
int index3 = 1;
int index5 = 1;
int indexNext = 2;
while (indexNext <= index) {
int min_val = Math.min(result[index2]*2, Math.min(result[index3]*3, result[index5]*5));
result[indexNext] = min_val;
while(result[index2]*2<=result[indexNext]) index2++;
while(result[index3]*3<=result[indexNext]) index3++;
while(result[index5]*5<=result[indexNext]) index5++;
indexNext++;
}
return result[index];
}
}
