Leetcode - ugly-number-ii

https://leetcode.com/problems/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. 

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Surprisingly this is a dp problem.

1 Declare an array for ugly numbers:  ugly[n]
2 Initialize first ugly no:  ugly[0] = 1
3 Initialize three array index variables i2, i3, i5 to point to 
   1st element of the ugly array: 
        i2 = i3 = i5 =0; 
4 Initialize 3 choices for the next ugly no:
         next_mulitple_of_2 = ugly[i2]*2;
         next_mulitple_of_3 = ugly[i3]*3
         next_mulitple_of_5 = ugly[i5]*5;
5 Now go in a loop to fill all ugly numbers till 150:
For (i = 1; i < n; i++ ) 
{
    /* These small steps are not optimized for good 
      readability. Will optimize them in C program */
    next_ugly_no  = Min(next_mulitple_of_2,
                        next_mulitple_of_3,
                        next_mulitple_of_5); 

    ugly[i] =  next_ugly_no       

    if (next_ugly_no  == next_mulitple_of_2) 
    {             
        i2 = i2 + 1;        
        next_mulitple_of_2 = ugly[i2]*2;
    } 
    if (next_ugly_no  == next_mulitple_of_3) 
    {             
        i3 = i3 + 1;        
        next_mulitple_of_3 = ugly[i3]*3;
     }            
     if (next_ugly_no  == next_mulitple_of_5)
     {    
        i5 = i5 + 1;        
        next_mulitple_of_5 = ugly[i5]*5;
     } 
     
}/* end of for loop */ 
6.return next_ugly_no

func nthUglyNumber(n int) int {
    if n == 1 {
        return 1
    }
    nums := make([]int, n)
    nums[0] = 1
    p2 := 0
    p3 := 0
    p5 := 0
    next2 := 2
    next3 := 3
    next5 := 5
    nextNumber := 1
    for i := 1; i < n; i++ {
        nextNumber = min(next2, min(next3, next5))
        nums[i] = nextNumber
        if nextNumber == next2 {
            p2++
            next2 = nums[p2]*2
        }
        if nextNumber == next3 {
            p3++
            next3 = nums[p3]*3
        }
        if nextNumber == next5 {
            p5++
            next5 = nums[p5]*5
        }
    }
    
    return nextNumber
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

• 相关文章
• 全局相关文章