Original link: leetcode-cn.com/problems/ug…

Answer:

  1. Refer to the detailed popular train of thought analysis, multi solution method in solution three.
  2. In the solution using the heap, each ugliness number is calculated by multiplying the previous smallest ugliness number by 2, 3, and 5 respectively, resulting in the following sequence:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15...

If you split it, it looks like this:

1, 1×2, 1×3, 2×2, 1×5, 2×3, 2×4, 3×3, 3×4, 3×5...

  1. According to the above rule, it can be divided into the following three groups according to each prime factor:
Times 2: 1×2, 2×2, 3×2, 4×2, 5×2, 6×2, 8×2, 9×2... Times 3: 1×3, 2×3, 3×3, 4×3, 5×3, 6×3, 8×3, 9×3... Times 5: 1×5, 2×5, 3×5, 4×5, 5×5, 6×5, 8×5, 9×5...Copy the code

We notice that the multiplicand behave the same way as ugly numbers.

  1. We can use three Pointers to represent the position of the multiplicand of the above three groups in the ugly sequence, and then we know the calculation it needs to perform. For example, if the current multiplied by two pointer points to an ugly number 5, it means that the current multiplied by two pointer needs to proceed5 x 2Operation.
  2. The smallest of the three Pointers is the value of the next ugly number. And the operation that’s being minimized is the one that’s actually being performed, so move the pointer one bit forward.
  3. In this way, cyclic calculation can ensure that the results of each calculation are optimal, which also ensures the order of ugly numbers from small to large, so that n times of calculation will get the NTH ugly number.
/ * * *@param {number} n
 * @return {number}* /
var nthUglyNumber = function (n) {
  let ugly = [1]; // Use an array to store ugly numbers in ascending order, with an initial value of 1 to ensure that the loop starts normally
  // A pointer to the position of ugly numbers 2, 3, and 5 in the ugly array
  let index3 = 0;
  let index2 = 0;
  let index5 = 0;

  // Loop to generate n ugly numbers and store them in array
  for (let i = 1; i < n; i++) {
    // Calculate the next set of ugliness numbers based on the ugliness numbers corresponding to the current 2, 3 and 5 prime factors respectively
    const newUgly2 = ugly[index2] * 2;
    const newUgly3 = ugly[index3] * 3;
    const newUgly5 = ugly[index5] * 5;
    // Minimizes a new set of ugly numbers
    const minUgly = Math.min(newUgly2, newUgly3, newUgly5);
    // Store the new ugly number into the ugly number group to ensure that the ugly array is sorted from small to large
    ugly.push(minUgly);

    // Only Pointers with the smallest value in the new set of ugly numbers need to be moved
    if (newUgly2 === minUgly) {
      index2++;
    }
    if (newUgly3 === minUgly) {
      index3++;
    }
    if(newUgly5 === minUgly) { index5++; }}// The last value of the ugly array is the NTH ugly number
  return ugly[ugly.length - 1];
};
Copy the code