The title

264. The 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

Idea 1: Violent solution

So the idea of the violent solution here is to take the ugly sequence and return it to the NTH one. Now, if you look at the ugly column, arr.

  1. Go through all the positive integers and see if they’re ugly, if they’re ugly, if they’re ugly, if they’re ugly, if they’re ugly, if they’re ugly, if they’re ugly, they’re ugly
  2. Judge arr length=n, jump out of the loop

Returns the last element.

But there’s a big problem here, if you judge a number to be ugly, right? So you have to recurse, divide by 2, 3, 5, all the way to the end, and see if there’s a remainder. Ugly number is not continuous, look for the 100th ugly number, the number of traversal is greater than 100, the more the more, plus this layer of recursion, that must be timed out.

So this plan is abandoned

Idea 2 Dynamic planning

Every ugly number except 1 is produced by multiplying 2, 3, and 5,

Careful analysis is just some ugly number multiplied by 2, or some ugly number multiplied by 3, or some ugly number multiplied by 5

Let’s say I have three numbers

1 (multiply each term of the ugly number by 2)

(1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2, 6 * 2, 8 * 2, 9 * 2, 10 * 2...].

Sequence 2 (multiply each term of the ugly sequence by 3)

(1 * 3, 2 * 3, 3 * 3, 4 * 3, 5 * 3, 6 * 3, 8 * 3, 9 * 3, 10 * 3...].

Number 3(multiply each term of the ugly number by 5)

[2 * 1 * 5, 5, 3 * 5, 4 * 5, 5 * 5, 6 * 5, 8 * 5, 9 * 5, 10 * 5...].

Suppose p2, P3 and P5 are the current Pointers of the three columns, and the Pointers start from 0. If each item in the column is selected into the ugly column, then the pointer ++. If there are two equal numbers at the same time, such as 3*5 and 5*3, then it doesn’t matter, everyone ++

If there is an ugly number column dp, the smallest number partition of the three columns is dp[p2]\*2,dp[p3]\*3,dp[p5]\*5, after excluding the number that has been selected as ugly number.

So every ugly number dp[I] = math.min (dp[p2]\*2,dp[p3]\*3,dp[p5]\*5), this is the state transition equation

Dp [0] = 1, is the boundary condition

So we can start building ugly columns

The code is as follows:

/ * * *@param {number} n
 * @return {number}* /
var nthUglyNumber = function(n) {
    let p2 = 0,p3 = 0,p5 = 0;
    let dp = [1];
    for(let i=0; i<n; i++){let min = Math.min(dp[p2]*2,dp[p3]*3,dp[p5]*5);
        if(dp[p2]*2 == min) p2++;
        if(dp[p3]*3 == min) p3++;
        if(dp[p5]*5 == min) p5++
        dp.push(min);
    }
    return dp[n-1]};Copy the code

Idea 3 small top heap

In combination with the analysis of idea 2, every ugly number is taken from these three sequences, and we do not need any Pointers now

To brute force, combine the above three numbers together and store them in a small top heap

Take the smallest ugly number X at the top of the small top heap each time, and push 3 ugly numbers into the small top heap, respectively 2*X,3*X,5*X

Start the heap empty and push the smallest ugly number, 1, into the heap.

You also need a hash table to do the reprocessing.

So the NTH time you take something from the heap, you get the NTH ugly number

var nthUglyNumber = function(n) {
    const baseArr = [2.3.5];
    const hashSet = new Set(a);const heap = new MinHeap();
    hashSet.add(1);
    heap.offer(1);
    let ugly = 0;
    for (let i = 0; i < n; i++) {
        ugly = heap.poll();
        for (const base of baseArr) {
            const next = ugly * base;
            if(! hashSet.has(next)) { hashSet.add(next); heap.offer(next); }}}return ugly;
};

/ / the minimum heap
class MinHeap {
    constructor() {
        this.heap = [];
    }
    offer(value) {
        this.heap.push(value);
        this.siftUp(this.heap.length - 1);
    }
    poll() {
        this.heap[0] = this.heap.pop();
        this.siftDown(0);
        return this.heap[0];
    }
    siftUp(index) {
        if(index === 0) { return; }
        const parentIndex = 2*index +1;
        if(this.heap[parentIndex] > this.heap[index]){
            [this.heap[parentIndex],this.heap[index]] = [this.heap[index],this.heap[parentIndex]]
            this.siftUp(parentIndex); }}siftDown(index) {
        const leftIndex = index * 2 + 1;
        const rightIndex = index * 2 + 2;
        if (this.heap[leftIndex] < this.heap[index]) {
            [this.heap[leftIndex],this.heap[index]] = [this.heap[index],this.heap[leftIndex]]
            this.siftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]){
            [this.heap[rightIndex],this.heap[index]] = [this.heap[index],this.heap[rightIndex]]
            this.siftDown(rightIndex); }}}Copy the code