LintCode Ugly Number 第 K 個醜數 優先隊列與 DP

問題

醜數定義：質因子只包含 3, 5, 7。求第 K 個醜數。序列：3, 5, 7, 9, 15, 21, 25, 27...

方法一：最小堆 + 去重集合 O(K log K)

long long kthPrimeNumber(int k) {
    priority_queue<long long, vector<long long>, greater<>> pq;
    unordered_set<long long> seen;
    pq.push(1); seen.insert(1);
    long long val = 1;
    for (int i = 0; i < k; ++i) {
        val = pq.top(); pq.pop();
        for (int p : {3,5,7}) {
            long long nxt = val * p;
            if (!seen.count(nxt)) {
                seen.insert(nxt);
                pq.push(nxt);
            }
        }
    }
    return val;
}

方法二：三指針 DP O(K) 時間 O(K) 空間

每個醜數由前面某醜數 ×3 或 ×5 或 ×7 得到。維護三指針 i3,i5,i7 指向下一個待乘的位置。

long long kthPrimeNumber(int k) {
    vector<long long> ugly(k+1);
    ugly[0] = 1;
    int i3=0, i5=0, i7=0;
    for (int i = 1; i <= k; ++i) {
        long long nxt = min({ugly[i3]*3, ugly[i5]*5, ugly[i7]*7});
        ugly[i] = nxt;
        if (nxt == ugly[i3]*3) ++i3;
        if (nxt == ugly[i5]*5) ++i5;
        if (nxt == ugly[i7]*7) ++i7;
    }
    return ugly[k];
}

複雜度對比

關鍵點

• 三指針各自獨立遞增，利用 if 而非 else if 處理相等情況（如 15=3×5=5×3）
• 初始 ugly[0]=1 作為種子
• K 從 1 開始計數（第 1 個醜數為 3）