LeetCode 筆記：超級醜數 解題詳解

一、題目描述

編寫一個程序來尋找第 n 個超級醜數。超級醜數是指其所有質因數都在給定質數列表 primes（大小為 k）中的正整數。例如，給定 primes = [2, 7, 13, 19]，前 12 個超級醜數序列為：[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]。

注意事項：

• 1 被視為任意質數列表的超級醜數。
• 給定的質數列表按升序排列。
• 約束條件：0 < k ≤ 100，0 < n ≤ 10^6，0 < primes[i] < 1000。

二、題目分析

核心任務是找出第 n 個只包含指定質因數的數字。這是一個經典的動態規劃與多指針問題。我們可以維護一個陣列 uglyNum 記錄已生成的超級醜數，並為每個質數維護一個指針 index，指向下一個待乘的醜數位置。每次從所有候選值（質數 × 對應指針位置的醜數）中選取最小值作為下一個超級醜數，並更新所有產生該最小值的指針。

三、示例代碼

class Solution {
public:
    int nthSuperUglyNumber(int n, vector& primes) {
        int len = primes.size();
        vector index(len, 0);
        vector uglyNum(n, INT_MAX);
        vector temp(len);
        uglyNum[0] = 1;
        for (int i = 1; i < n; ++i) {
            int minj = -1;
            int minNum = INT_MAX;
            for (int j = 0; j < len; ++j) {
                temp[j] = primes[j] * uglyNum[index[j]];
                if (temp[j] < uglyNum[i]) {
                    minNum = temp[j];
                    uglyNum[i] = temp[j];
                    minj = j;
                }
            }
            for (int j = minj; j < len; ++j) {
                if (minNum == temp[j]) ++index[j];
            }
        }
        return uglyNum[n - 1];
    }
};

四、小結

此解法利用多指針思想，時間複雜度為 O(n × k)，空間複雜度 O(n + k)。雖然代碼行數稍多，但通過輔助陣列 temp 避免重複計算，提升了效率。對於 n ≤ 10^6 且 k ≤ 100 的數據範圍，此解法完全可行。