解題說明
Ugly Number II
題目描述：醜數（Ugly Number）是指質因數只含 2、3、5 的正整數（1 視為醜數）。給定整數 n，回傳第 n 個醜數。
解題思路：使用動態規劃三指針法，維護三個指針 p2、p3、p5，分別追蹤下一個要乘以 2、3、5 的醜數索引。每次取三者乘積的最小值作為下一個醜數，並將對應指針前進。
建立陣列 dp，其中 dp[i] 代表第 i+1 個醜數。初始化 dp[0] = 1。每一步：
next2 = dp[p2] * 2next3 = dp[p3] * 3next5 = dp[p5] * 5dp[i] = min(next2, next3, next5)- 若
dp[i] == next2則p2++；若等於next3則p3++；若等於next5則p5++（可同時移動多個指針，避免重複）
此方法保證每個醜數按升序生成，且不會遺漏或重複。最終回傳 dp[n-1]。
C++ 解法
複雜度分析
時間複雜度：O(n) — 只需一次線性掃描，每步三個乘法與比較均為 O(1)，生成 n 個醜數共需 n 步。
空間複雜度：O(n) — 需要大小為 n 的 dp 陣列儲存所有醜數。若只需要第 n 個值且不保留前面結果，空間難以進一步壓縮，因為三個指針均需回查之前的醜數。
虛擬碼
1. Create array dp of size n; set dp[0] = 1. 2. Initialize pointers p2 = 0, p3 = 0, p5 = 0. 3. For i from 1 to n-1: a. Compute next2 = dp[p2]*2, next3 = dp[p3]*3, next5 = dp[p5]*5. b. Set dp[i] = min(next2, next3, next5). c. If dp[i] == next2: increment p2. d. If dp[i] == next3: increment p3. e. If dp[i] == next5: increment p5. 4. Return dp[n-1].
其他解法
方法一：最小堆（Min-Heap）
使用最小堆儲存候選醜數。初始放入 1，每次取出最小值後分別推入其乘以 2、3、5 的結果。需用 unordered_set 去重以避免重複入堆。時間複雜度 O(n log n)，空間複雜度 O(n)。比三指針法慢且代碼更繁瑣，但思路更直觀。
方法二：暴力枚舉 從 1 開始逐一判斷每個正整數是否為醜數（反覆除以 2、3、5 直到餘 1），計數到第 n 個。時間複雜度極高，因為相鄰醜數間距可能很大（如第 1690 個醜數為 2^31 量級），不適合 n 較大的情況。
方法三：數學公式 + 排序
枚舉所有 2^a * 3^b * 5^c 的組合（a, b, c ≥ 0）並排序，取第 n 個。需要預估範圍 a、b、c 的上界，實作較繁，且排序耗費額外時間，競程中較少使用。
延伸思考
- 超級醜數（LeetCode 313）將質因數推廣到任意給定的質數陣列，三指針方法如何推廣到 k 個指針？時間與空間複雜度如何變化？
- 若要回傳第 n 個醜數的「下標」（在所有正整數中排第幾位），是否有辦法不生成所有醜數而直接計算？
- 本題的三指針方法與歸併 k 條有序串流的模式有何相似之處？能否用相同框架解決其他「多倍數合併」問題？