264. 丑数 II
题目描述
丑数指的是质因数只有 2、3、5 的正整数，1 也视为丑数。
输入一个整数 n。把所有丑数从小到大排成一列，返回其中第 n 个（从 1 开始计数）。
示例 1
输入：n = 10 输出：12
解释：前 10 个丑数是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12，第 10 个是 12。
示例 2
输入：n = 1 输出：1
解释：第 1 个丑数是 1。
数据范围
1 <= n <= 1690
解题思路：三指针动态规划
每个丑数（除 1 外）都是更小的某个丑数乘 2、3 或 5 得到的。把丑数序列 dp 看成三条有序流：dp*2、dp*3、dp*5，用三个指针 p2、p3、p5 指向各流中下一个待用的位置，每次取三者最小值作为下一个丑数，并把所有等于它的指针前移（去重）。
为什么正确
dp[0..i-1] 是前 i 个丑数（严格递增）；dp[p2]*2、dp[p3]*3、dp[p5]*5 都大于 dp[i-1]，且是各流中最小的未用值。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
三个 if 必须是并列的而不是 elif：多个候选同时等于最小值时（如 6=2*3=3*2）要一起前移，否则会出现重复的丑数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [1] * n
p2 = p3 = p5 = 0
for i in range(1, n):
a, b, c = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
dp[i] = min(a, b, c)
if dp[i] == a:
p2 += 1
if dp[i] == b:
p3 += 1
if dp[i] == c:
p5 += 1
return dp[n - 1]class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n]; dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int a = dp[p2] * 2, b = dp[p3] * 3, c = dp[p5] * 5;
dp[i] = Math.min(a, Math.min(b, c));
if (dp[i] == a)
p2++;
if (dp[i] == b)
p3++;
if (dp[i] == c)
p5++;
}
return dp[n - 1];
}
}class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n, 1);
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int a = dp[p2] * 2, b = dp[p3] * 3, c = dp[p5] * 5;
dp[i] = min({a, b, c});
if (dp[i] == a)
p2++;
if (dp[i] == b)
p3++;
if (dp[i] == c)
p5++;
}
return dp[n - 1];
}
};func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
p2, p3, p5 := 0, 0, 0
for i := 1; i < n; i++ {
a, b, c := dp[p2]*2, dp[p3]*3, dp[p5]*5
dp[i] = min(a, b, c)
if dp[i] == a {
p2++
}
if dp[i] == b {
p3++
}
if dp[i] == c {
p5++
}
}
return dp[n-1]
}var nthUglyNumber = function(n) {
const dp = new Array(n).fill(1);
let p2 = 0, p3 = 0, p5 = 0;
for (let i = 1; i < n; i++) {
const a = dp[p2] * 2, b = dp[p3] * 3, c = dp[p5] * 5;
dp[i] = Math.min(a, b, c);
if (dp[i] === a)
p2++;
if (dp[i] === b)
p3++;
if (dp[i] === c)
p5++;
}
return dp[n - 1];
};function nthUglyNumber(n: number): number {
const dp: number[] = new Array(n).fill(1);
let p2 = 0, p3 = 0, p5 = 0;
for (let i = 1; i < n; i++) {
const a = dp[p2] * 2, b = dp[p3] * 3, c = dp[p5] * 5;
dp[i] = Math.min(a, b, c);
if (dp[i] === a)
p2++;
if (dp[i] === b)
p3++;
if (dp[i] === c)
p5++;
}
return dp[n - 1];
}其他解法
最小堆先生成候选再挑最小值，O(n log n)；三指针利用“每个丑数都由更小的丑数乘 2、3、5 得到”，按序合并三个序列，O(n) 且自带去重。
解法 2：最小堆 + 哈希去重 时间 O(n log n)，空间 O(n)
最小堆初始只有 1。每次弹出堆顶 x，它就是下一个最小的丑数；再把 2x、3x、5x 中没见过的放入堆，用哈希集合去重。第 n 次弹出的数就是答案。
思路直观，容易推广到任意质因子集合。堆操作 O(log n)，还要额外的去重集合；堆中的数会超过答案范围，需要用 64 位整数。
import heapq
class Solution:
def nthUglyNumber(self, n: int) -> int:
heap = [1]
seen = {1}
for _ in range(n - 1):
x = heapq.heappop(heap)
for p in (2, 3, 5):
y = x * p
if y not in seen:
seen.add(y)
heapq.heappush(heap, y)
return heap[0]class Solution {
public int nthUglyNumber(int n) {
PriorityQueue<Long> heap = new PriorityQueue<>();
Set<Long> seen = new HashSet<>();
heap.offer(1L);
seen.add(1L);
for (int i = 1; i < n; i++) {
long x = heap.poll();
for (int p : new int[]{2, 3, 5}) {
long y = x * p;
if (seen.add(y)) heap.offer(y);
}
}
return (int) (long) heap.peek();
}
}class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<long long, vector<long long>, greater<long long>> heap;
unordered_set<long long> seen{1};
heap.push(1);
for (int i = 1; i < n; i++) {
long long x = heap.top();
heap.pop();
for (int p : {2, 3, 5}) {
long long y = x * p;
if (seen.insert(y).second) heap.push(y);
}
}
return (int)heap.top();
}
};type minHeap []int
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func nthUglyNumber(n int) int {
h := &minHeap{1}
seen := map[int]bool{1: true}
for i := 1; i < n; i++ {
x := heap.Pop(h).(int)
for _, p := range []int{2, 3, 5} {
y := x * p
if !seen[y] {
seen[y] = true
heap.Push(h, y)
}
}
}
return (*h)[0]
}var nthUglyNumber = function(n) {
const heap = [1];
const push = (v) => {
heap.push(v);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0], last = heap.pop();
if (heap.length) {
heap[0] = last;
let i = 0;
while (true) {
let m = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < heap.length && heap[l] < heap[m]) m = l;
if (r < heap.length && heap[r] < heap[m]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
const seen = new Set([1]);
for (let i = 1; i < n; i++) {
const x = pop();
for (const p of [2, 3, 5]) {
const y = x * p;
if (!seen.has(y)) {
seen.add(y);
push(y);
}
}
}
return heap[0];
};function nthUglyNumber(n: number): number {
const heap: number[] = [1];
const push = (v: number) => {
heap.push(v);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = (): number => {
const top = heap[0], last = heap.pop()!;
if (heap.length) {
heap[0] = last;
let i = 0;
while (true) {
let m = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < heap.length && heap[l] < heap[m]) m = l;
if (r < heap.length && heap[r] < heap[m]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
const seen = new Set<number>([1]);
for (let i = 1; i < n; i++) {
const x = pop();
for (const p of [2, 3, 5]) {
const y = x * p;
if (!seen.has(y)) {
seen.add(y);
push(y);
}
}
}
return heap[0];
}