“This is the 17th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

We call numbers that contain only the prime factors 2, 3, and 5 Ugly numbers. Find the NTH ugly number in ascending order.

  • Example 1:
Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 are the first 10 ugly numbers.Copy the code
  • prompt
1 is the ugly number. N The value cannot exceed 1690.Copy the code

parsing

An ugly number is a positive integer whose prime factors include only 2, 3 and 5. Number 1 is ugly

1. The core is this sentence: ensure that every ugly number at each position has a chance to generate 2, 3, 5, and do not miss a value!

2. At the end of the loop, ensure that the ugly numbers at each position have completed 2, 3, and 5 operations! It’s just that duplicate values don’t double count

3. Ensure that each ugly number completes the operations 2, 3, and 5. For example, if the ugly number pointed to by B completes the operations 3, it is b++.

4. If this happens: If dp[a] * 2 == dp[b] * 3, then both a and B have completed the increment, indicating that dp[a] has completed the 2 operation, dp[b] has completed the 3 operation, so the next ugly number that needs to complete 2 operation is dp[a+1], and the next ugly number that needs to complete 3 operation is dp[b+1].

The sample

class Solution { public int nthUglyNumber(int n) { int[] dp = new int[n]; // initialize the array dp[0] = 1; int a=0,b=0,c=0; for(int i=1; i<n; i++){ dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5); if(dp[i] == dp[a]*2) a++; if(dp[i] == dp[b]*3) b++; if(dp[i] == dp[c]*5) c++; } return dp[n-1]; }}Copy the code

Running results:

Result: Yes

Execution time: 2 ms, beating 99.62% of all Java commits

Memory consumption: 37.4 MB, beating 73.38% of all Java commits

There is also the minimum heap algorithm:

To get the NNTH ugly number from small to large, we can use the minimum heap implementation. The heap is initially empty. First add the smallest ugly number, 11, to the heap. Each time the top element xx is removed, xx is the smallest ugly number in the heap. Since 2x,3x, 5x2x,3x, and 5x are also ugly numbers, add 2X,3x, 5x2x,3x, and 5x to the heap.

class Solution { public int nthUglyNumber(int n) { int[] factors = {2, 3, 5}; Set<Long> seen = new HashSet<Long>(); PriorityQueue<Long> heap = new PriorityQueue<Long>(); seen.add(1L); heap.offer(1L); int ugly = 0; for (int i = 0; i < n; i++) { long curr = heap.poll(); ugly = (int) curr; for (int factor : factors) { long next = curr * factor; if (seen.add(next)) { heap.offer(next); } } } return ugly; }}Copy the code