Ugly number is a number that only have factors 2, 3 and 5.
Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
通过空间代价来提升时间复杂度。
创建一个数组，长度为n，根据n位的丑数是前面的丑数乘2、乘3或乘5所得，比较所得最小的数就是最新的丑数。
算过一次之后，该因子的基数加一，避免重复计算。
public class Solution { /** * @param n: An integer * @return: the nth prime number as description. */ public int nthUglyNumber(int n) { // write your code here int[] ugly = new int[n]; ugly[0] = 1; int nextUglyIndex = 1;
int mul2 = 0; int mul3 = 0; int mul5 = 0; int min = 0; while(nextUglyIndex<n){ min = compare_min(ugly[mul2]*2,ugly[mul3]*3,ugly[mul5]*5); ugly[nextUglyIndex] = min; while(ugly[mul2]*2<=ugly[nextUglyIndex]){ mul2++; } while(ugly[mul3]*3<=ugly[nextUglyIndex]){ mul3++; } while(ugly[mul5]*5<=ugly[nextUglyIndex]){ mul5++; }
nextUglyIndex++;
} int result = ugly[n - 1]; return result; } public int compare_min(int a,int b,int c){ if(a<=b){ if(a<=c) return a; return c; }else if(c<=b){ return c; } return b; } }
