LeetCode_ Dynamic programming_ Medium_ 264. Ugly number II

1. subject

Give you an integer n , Please find out and go back to n Ugly number .

Ugly number That is, only the prime factor is included 2、3 and / or 5 The positive integer .

Example 1：
Input ：n = 10
Output ：12
explain ：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] It's from the front 10 A sequence of ugly numbers .

Example 2：
Input ：n = 1
Output ：1
explain ：1 It's usually considered ugly .

Tips ：
1 <= n <= 1690

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/ugly-number-ii

2. Ideas

（1） The law of violent exhaustion
Violent exhaustion is easier to think of ：
① If n == 1, Then return directly 1, because 1 It's usually considered ugly ;
② Otherwise, from a positive integer x = 2 Start judging , For specific judgment methods, please refer to LeetCode_263. Ugly number This article , If the current number is ugly , be n–, When n == 1 Stop judging when , At this time x - 1 That is the first. n Ugly number . However, the time complexity of this method is high , stay LeetCode When submitting on “ Time limit exceeded ” A hint of ！

（2） The smallest pile
Train of thought reference Official solution to this problem .

（3） Dynamic programming
Train of thought reference Official solution to this problem .

3. Code implementation （Java）

// Ideas 1———— The law of violent exhaustion 
class Solution {
    
    public int nthUglyNumber(int n) {
    
        int[] factors = {
    2, 3, 5};
        if (n == 1) {
    
            // 1  It's usually considered ugly 
            return 1;
        }
        // From positive integers  2  Start judging 
        int x = 2;
        int i = 1;
        while (n > 1) {
    
            int tmp = x;
            for (int j = 0; j < factors.length; j++) {
    
                while (tmp % factors[j] == 0) {
    
                    tmp /= factors[j];
                }
            }
            if (tmp == 1) {
    
                n--;
            }
            // Determine the next positive integer 
            x++;
        }
        return x - 1;
    }
}

// Ideas 2———— The smallest pile 
class Solution {
    
    public int nthUglyNumber(int n) {
    
        int[] factors = {
    2, 3, 5};
        if (n == 1) {
    
            // 1  It's usually considered ugly 
            return 1;
        }
        Set<Long> hashSet = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        hashSet.add(1L);
        // Initially, the heap is empty , First, the smallest ugly number  1  Add heap 
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
    
            //  Every time you take out the top element  x, be  x  Is the smallest ugly number in the heap 
            long x = heap.poll();
            ugly = (int) x;
            for (int factor : factors) {
    
                /*  because  2x, 3x, 5x  It's also an ugly number , So it will  2x, 3x, 5x  Add heap   This will result in duplicate elements in the heap , To avoid repeating elements , Here we use hash set to remove duplication   In the case of excluding duplicate elements , The first  n  The element extracted from the smallest heap for the second time is the  n  Ugly number  */
                long next = x * factor;
                if (hashSet.add(next)) {
    
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }
}

// Ideas 3———— Dynamic programming 
class Solution {
    
    public int nthUglyNumber(int n) {
    
        // dp[i]  It means the first one  i  Ugly number 
        int[] dp = new int[n + 1];
        //  The smallest ugly number is  1
        dp[1] = 1;
        // Define three pointers , Indicates that the next ugly number is the ugly number pointed by the current pointer multiplied by the corresponding prime factor 
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
    
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
    
                p2++;
            }
            if (dp[i] == num3) {
    
                p3++;
            }
            if (dp[i] == num5) {
    
                p5++;
            }
        }
        return dp[n];
    }
}