剑指offer丑数：动态规划+最小堆（JavaScript实现）

时间复杂度是\(O(N)\)，空间复杂度是\(O(N)\)。

解法 2: 最小堆

借助最小堆，可以在 \(O(LogN)\) 时间复杂度内找到当前最小的元素。整体算法流程是：

• 准备最小堆 heap。准备 map，用于记录丑数是否出现过。
• 将 1 放入堆中
• 从 0 开始，遍历 n 次：
  • 取出堆顶元素，放入数组 res 中
  • 用堆顶元素依此乘以 2、3、5
  • 检查结果是否出现过。若没有出现过，那么放入堆中，更新 map
• 返回 res 最后一个数字

代码实现如下：

// ac地址：https://leetcode-cn.com/problems/ugly-number-ii/
// 原文地址：https://xxoo521.com/2020-03-10-ugly-number-ii/

const defaultCmp = (x, y) => x > y;
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
class Heap {
    /**
     * 默认是最大堆
     * @param {Function} cmp
     */
    constructor(cmp = defaultCmp) {
        this.cOntainer= [];
        this.cmp = cmp;
    }

    insert(data) {
        const { container, cmp } = this;

        container.push(data);
        let index = container.length - 1;
        while (index) {
            let parent = Math.floor((index - 1) / 2);
            if (!cmp(container[index], container[parent])) {
                return;
            }
            swap(container, index, parent);
            index = parent;
        }
    }

    extract() {
        const { container, cmp } = this;
        if (!container.length) {
            return null;
        }

        swap(container, 0, container.length - 1);
        const res = container.pop();
        const length = container.length;
        let index = 0,
            exchange = index * 2 + 1;

        while (exchange  x