丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
思路
方案1： 利用最小堆 - 使用一个集合记录每次与因子乘积后的值，并且把它添加入最小堆 - 不断pop最小堆，知道到达第n的次数得到的堆顶元素即是所求
方案2： 利用动态规划
代码
// 方案1 代码
// 最小堆实现
function nthUglyNumber(n) {
const factors = [2, 3, 5];
const heap = new MinHeap();
const seen = new Set();
heap.insert(1);
seen.add(1);
let ugly = 0;
for (let i=0; i<n; i++) {
ugly = heap.pop();
for (const factor of factors) {
const next = factor * ugly;
if (!seen.has(next)) {
seen.add(next);
heap.insert(next);
}
}
}
return ugly;
}
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(childIndex) {
return (childIndex - 1) >> 1;
}
getLeftChildIndex(parentIndex) {
return parentIndex*2 + 1;
}
getRightChildIndex(parentIndex) {
return parentIndex*2 + 2;
}
insert(val) {
this.heap.push(val);
this.shiftUp(this.heap.length - 1);
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0);
return this.heap[0];
}
shiftUp(index) {
if (index === 0) return;
let parentIndex = this.getParentIndex(index);
let leftChildIndex = this.getLeftChildIndex(parentIndex);
let rightChildIndex = this.getRightChildIndex(parentIndex);
let minIndex = leftChildIndex;
if (this.heap[rightChildIndex] && this.heap[rightChildIndex] < this.heap[leftChildIndex]) {
minIndex = rightChildIndex;
}
if (this.heap[minIndex] < this.heap[parentIndex]) {
this.swap(minIndex, parentIndex);
}
this.shiftUp(parentIndex);
}
shiftDown(index) {
let leftChildIndex = this.getLeftChildIndex(index);
let rightChildIndex = this.getRightChildIndex(**index**);
if (!this.heap[leftChildIndex] && !this.heap[rightChildIndex]) return;
let minIndex = leftChildIndex;
if (this.heap[rightChildIndex] && this.heap[leftChildIndex] > this.heap[rightChildIndex]) {
minIndex = rightChildIndex;
}
if (this.heap[minIndex] < this.heap[index]) {
this.swap(minIndex, index);
}
this.shiftDown(minIndex);
}
swap(left, right) {
const temp = this.heap[left];
this.heap[left] = this.heap[right];
this.heap[right] = temp;
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
// 方案2 代码
// 动态规划实现
function nthUglyNumber(n) {
let dp = [];
dp[1] = 1;
let p2 = 1, p3 = 1, p5 = 1;
for (let i=2; i<=n; i++) {
const pNum2 = dp[p2] * 2;
const pNum3 = dp[p3] * 3;
const pNum5 = dp[p5] * 5;
dp[i] = Math.min(Math.min(pNum2, pNum3), pNum5);
if (dp[i] === pNum2) {
p2++;
}
if (dp[i] === pNum3) {
p3++;
}
if (dp[i] === pNum5) {
p5++;
}
}
return dp[n];
}
复杂度分析
方案1：
- 时间复杂度: O(NlogN)
- 空间复杂度: O(N)
方案2：
- 时间复杂度: O(N)
- 空间复杂度: O(N)