利用堆排序很容易進行查找
質數又稱素數，一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數，
質因數（素因數或質因子）在數論里是指能整除給定正整數的質數，除了1以外，兩個沒有其他共同質因子的正整數稱為互質，因為1沒有質因子，1與任何正整數（包括1本身）都是互質
把只包含質因子2、3和5的數稱作丑數（Ugly Number），例如6、8都是丑數，但7.14不是，因為它們包含質因子7， 習慣上我們把1當做是第一個丑數
class Ugly {
constructor (n, primes) {
this.n = n
this.primes = new Heap(primes)
}
getAll () {
// 超級丑數串列
let res = [1]
let i = 2
let primes = this.primes
// 不知道上限用while回圈
while (res.length < this.n) {
let arr = Ugly.getPrimies(i)
let k = 0
let l = arr.length
for (; k < l; k++) {
if (!primes.find(arr[k])) {
break
}
}
// k===l有兩種情況，1.壓根沒有質因數，2.質因數都在指定串列中
if (k === l) {
if (l === 0) {
if (primes.find(i)) {
res.push(i)
}
} else {
res.push(i)
}
}
i++
}
// 回傳丑數陣列
return res[this.n - 1]
}
// 計算指定正整數n的質因數
static getPrimies (n) {
let prime = (n) => {
let arr = []
for (let i = 2; i < n / 2 + 1; i++) {
// 求質數利用遞回，因為回傳的是一個arr陣列,當陣列為空時說明是質數
if (n % i === 0 && !prime(i).length) {
arr.push(i)
}
}
return arr
}
return prime(n)
}
}
class Heap {
constructor (arr) {
this.data = https://www.cnblogs.com/firebet/p/arr
this.max = arr.length
this.sort()
}
sort () {
let iArr = this.data
let n = iArr.length
if (n <= 1) {
return iArr
} else {
// 回圈是為了遍歷每一個可能要調整的節點，maxHeapify內部遞回是為了回復被破壞的堆
for (let i = Math.floor(n / 2); i >= 0; i--) {
Heap.maxHeapify(iArr, i, n)
}
return iArr
}
}
find (val, i = 0) {
let arr = this.data
if (val > arr[i] || i > this.max) {
return false
} else if (val === arr[i]) {
return val
} else {
return this.find(val, i * 2 + 1) || this.find(val, i * 2 + 2)
}
}
static swap (arr, a, b) {
if (a === b) {
return''
}
// 交換
let c = arr[a]
arr[a] = arr[b]
arr[b] = c
}
// 構建最大堆
static maxHeapify (Arr, i, size) {
// 左節點
let l = i * 2 + 1
// 右節點
let r = i * 2 + 2
let largest = i
// 父節點和左節點l作比較獲取最大
if (l <= size && Arr[l] > Arr[largest]) {
largest = l
}
// 右節點額最大值比較
if (r <= size && Arr[r] > Arr[largest]) {
largest = r
}
if (largest !== i) {
Heap.swap(Arr, i, largest)
Heap.maxHeapify(Arr, largest, size)
}
}
}
export default Ugly
export {
Heap
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24708.html
標籤：其他
上一篇：前端的資料結構
下一篇：超級丑數--用查找的api解決