LeetCode Ugly Number II：求第 n 個醜數 — 三指針動態規劃

題目描述

求第 n 個醜數。醜數序列：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

解題思路：三指針法

維護三個指針 i2, i3, i5 分別指向下一個乘以 2、3、5 可能產生新醜數的位置。每次取三者乘積的最小值作為下一個醜數，並移動對應指針（可能多個指針同時移動）。

參考代碼 (C++)

class Solution {
public:
    int nthUglyNumber(int n) {
        vector ugly(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 = min(next2, min(next3, next5));
            ugly[i] = next;
            if (next == next2) ++i2;
            if (next == next3) ++i3;
            if (next == next5) ++i5;
        }
        return ugly[n-1];
    }
};

複雜度分析

• 時間：O(n) —— 單次遍歷。
• 空間：O(n) —— 存儲前 n 個醜數。