Leetcode 264 Ugly Number II

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.

Solution 1: Use a array to store the ugly number array. Maintain the index f2, f3, f5. which nums[f2]*2, nums[f3]*3 and nums[f5]*5 is just above the current value, in other words, nums[i]=min{2*nums[f2], 3*nums[f3], 5*nums[f5]}.

 public class Solution {  
   public int nthUglyNumber(int n) {  
     if (n<=0) return 0;  
     int[] ugly=new int[n];  
     ugly[0]=1;  
     int f2=2, f3=3, f5=5;  
     int i=0, j=0, k=0;  
     for (int t=1; t<n; t++) {  
       int min=Math.min(f2,Math.min(f3,f5));  
       ugly[t]=min;//could be f2=f3=f5, if any of them equal min, need to move to next  
       if (min==f2) f2=ugly[++i]*2;  
       if (min==f3) f3=ugly[++j]*3;  
       if (min==f5) f5=ugly[++k]*5;  
     }  
     return ugly[n-1];  
   }  
 }