題目描述

求第 n 個醜數。醜數序列：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...（質因數僅 2,3,5）。

核心洞察：合併三個有序序列

每個醜數 = 某較小醜數 × 2 或 ×3 或 ×5。維護三個指針 i2, i3, i5 分別指向下一個乘以 2、3、5 產生新醜數的位置：

• next2 = ugly[i2] * 2
• next3 = ugly[i3] * 3
• next5 = ugly[i5] * 5
• 下一醜數 = min(next2, next3, next5)
• 哪個指針產生了最小值，該指針++（多個相等則都++，去重）

完整代碼

// Runtime: 9 ms
public class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < n; i++) {
            int next2 = ugly[i2] * 2;
            int next3 = ugly[i3] * 3;
            int next5 = ugly[i5] * 5;
            int next = Math.min(next2, Math.min(next3, next5));
            ugly[i] = next;
            if (next == next2) i2++;
            if (next == next3) i3++;
            if (next == next5) i5++;
        }
        return ugly[n - 1];
    }
}

算法演示（前 10 個）

複雜度分析

• 時間：O(n) —— 單次遍歷，每步常數操作
• 空間：O(n) 存儲醜數數組（可優化為 O(1) 僅保留最後幾個，但通常需返回第 n 個）

關鍵去重邏輯

獨立 if 而非 else if，確保 6 = 2×3 = 3×2 時 i2 和 i3 都前進，避免重複生成 6。