关于超级丑数超时问题

来源:12-6 超级丑数-代码演示(2)

meimei1314

2020-02-23

您好,老师。以下是根据您的思路,写的代码。在执行leetcode题中,出现了超时的问题。虽然,自己想过解决,但是实在找不到解题思路。烦请老师解惑。
var nthSuperUglyNumber = function(n, primes) {
    if (!primes.length) {
        return []
    }
    let maxHeapify = heap(primes)
    let res = [1]
    let num = 2
    while(res.length<n) {
        let arr = getPrimes(num)
        let i = 0, length = arr.length;
        for (; i<length; i++) {
            if (!searchHeap(maxHeapify, arr[i], 0)) {
                break
            }
        }
        if (i === length) {
            if (i===0 && searchHeap(maxHeapify, arr[i], 0)) {
                res.push(num)
            } else if (i !== 0) {
                res.push(num)
            }
        }
        num++
    }
    return res.pop()
};
function getPrimes(n, arr = []) {
    for (let i=2,length = Math.floor(n/2)+1; i<length; i++) {
        if (n%i===0 && getPrimes(i).length===0) {
            arr.push(i)
        }
    }
    return arr
}
function heap(arr) {
    let size = arr.length;
    let i=Math.floor(size/2)-1;
    for (; i>=0; i--) {
        maxHeap(arr, i, size)
    }
    return arr
}
function maxHeap(arr, i, size) {
    let left = 2*i+1;
    let right = 2*i+2;
    let largest = i
    if (left<size && arr[left]>arr[i]) {
        largest = left
    }
    if (right<size && arr[right]>arr[largest]) {
        largest = right
    }
    if (largest !== i) {
        maxHeap(arr, largest, size)
    }
}
function searchHeap(arr, val, i) {
    if (!arr[i]) {
        return false
    }
    if (val>arr[i]) {
        return false
    } else if (val === arr[i]) {
        return false
    } else {
        return searchHeap(arr, val, 2*i+1) || searchHeap(arr, val, 2*i+2)
    }
}

图片描述
// 测试用例
800
[37,43,59,61,67,71,79,83,89,97,101,103,113,127,131,157,163,167,173,179,191,193,197,199,211,229,233,239,251,257]

写回答

1回答

快乐动起来呀

2020-02-24

目前是用了递归,递归在LeetCode这边都会超时,这个我们再想下不用递归的方案

0
0

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程