LeetCode 313: Super Ugly Number ·

基本資料
#

難易度: medium 第一次嘗試：2022-11-16

提交紀錄：Wrong Answer ×2 → Output Limit Exceeded → Accepted → Wrong Answer → Accepted → Output Limit Exceeded → Wrong Answer → Output Limit Exceeded → Wrong Answer

解題思路
#

跟 LC 264 一樣，每個質數 p 有一個指針 idx[p]，下一個數是所有 u[idx[p]] * p 的最小值，等於它的指針都前進，O(nk)。

用 heap 的寫法要處理重複：例如 6 會從 2 × 3 和 3 × 2 各被推一次。一個技巧是彈出 x 之後只乘上不超過 x 最小質因數的質數（遇到 x % p == 0 就停），這樣每個數只會被它「最小質因數 × 剩下的部分」產生一次（Heap）。

我的嘗試
#

這題用 heap 寫，錯了 8 次，都跟重複有關：

2022-11-16：彈出 p 後把它乘上每個質數推進去，只在 p == prime 時停，這只有在 p 本身是質數時才會停，像 6 這種合數還是會產生重複，同一個數被彈出兩次，答案往前錯位。
2022-11-26：有幾版拿掉了停止條件，重複更多；把條件改成 p % prime == 0（乘到 p 的最小質因數就停）才 AC。中間還有三次是 print 造成的 Output Limit Exceeded。

正確解法
#

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        u = [1]
        idx = [0] * len(primes)
        while len(u) < n:
            nxt = min(u[idx[k]] * p for k, p in enumerate(primes))
            u.append(nxt)
            for k, p in enumerate(primes):
                if u[idx[k]] * p == nxt:
                    idx[k] += 1
        return u[-1]