leetcode 264. Ugly Number II

Seawolf

1. Write a program to find the n-th ugly number.
   
2. 
   
3. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
   
4. 
   
5. Example:
   
6. 
   
7. Input: n = 10
   
8. Output: 12
   
9. Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
   
10. Note:  
    
11. 
    
12. 1 is typically treated as an ugly number.
    
13. n does not exceed 1690.

复制代码

1. class Solution {
   
2.     public int nthUglyNumber(int n) {
   
3.         int[] arr = new int[n+1];
   
4.         int t2 = 1, t3 = 1, t5 = 1;
   
5.         arr[1] = 1;
   
6.         for(int i = 2 ; i <= n ; i++){
   
7.             arr[i] = Math.min (Math.min(2*arr[t2], 3*arr[t3]),5*arr[t5]);
   
8.             
   
9.             if(arr[i] == 2*arr[t2]) t2++;
   
10.             if(arr[i] == 3*arr[t3]) t3++;
    
11.             if(arr[i] == 5*arr[t5]) t5++;
    
12.         }
    
13.         
    
14.         return arr[n];
    
15.         
    
16.     }
    
17.    
    
18. }

复制代码