关于超级丑数超时问题
来源: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这边都会超时,这个我们再想下不用递归的方案
00
相似问题