Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

The title

Ugly number II: given an integer n, please find and return the NTH ugly number. Ugly numbers are positive integers that contain only prime factors 2, 3, and/or 5. Example 1:

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

Example 2:

Input: n = 1 Output: 1 Explanation: 1 is usually considered ugly.Copy the code

Tip:

  • 1 <= n <= 1690

Answer key

Analysis of the problem solving

Antithesis thought

  1. Define three Pointers p2, P3, p5;
  2. In the 2-n interval, the NTH ugliness is zeroDp [n] = min(DP [p2]×2, DP [p3]×3, DP [p5]×5);
  3. The corresponding Pointers of P2, P3 and P5 increase;
  4. The same goes for the rest of the sequence, so you can see what happens in the code

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(n)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        // 1 Set the default value
        dp[1] = 1 ;
        // define three Pointers: p2, p3, p5
        int p2 = 1, p3 = 1, p5 = 1;
        for(int i = 2; i <= n; i++) {
            // Get the values of the three Pointers
            int num2 =dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5; 
            // Get the minimum value
            dp[i] = Math.min(Math.min(num2, num3), num5);
            / / p2 accumulation
            if (dp[i] == num2) {
                p2++;
            }
            / / p3 accumulation
            if (dp[i] == num3) {
                p3++;
            }
            / / p5 accumulation
            if(dp[i] == num5) { p5++; }}returndp[n]; }}Copy the code

Feedback results after submission:

The problem solving to summarize

  • This is a standard sequence of numbers problemDynamic programming,The minimum heapSolution to the problem.
  • In this problem, the hardest part is actually deriving the NTH value of a sequence from three counts and the result of the calculation.
  • If we encounter this problem in production or in the real world, we can remember the pattern, first locate the pattern, and then solve the problem in detail.

The reference information

  • LeetCode 264: Ugly number II