ZeroJudge 解題筆記：d129. 00136 - Ugly Numbers

作者：王一哲
日期：2026年4月16日


ZeroJudge 題目連結：d129. 00136 - Ugly Numbers

解題想法

將找到的 ugly number 存入串列 $ugly$ 之中，再用 3 個變數 $i, j, k$ 分別儲存目前串列之中最後一個 $2, 3, 5$ 的倍數索引值。用 while 迴圈，執行到串列的長度等於 1500 為止，裡面再用 3 個 while 迴圈，更新 $i, j, k$ 的值，更新完之後再取 $ugly[i]*2, ugly[j]*3, ugly[k]*5$ 的最小值，就是新的 ugly number。

Python 程式碼

使用時間約為 7 ms，記憶體約為 8.4 MB，通過測試。

ugly = [1]
i, j, k = 0, 0, 0  # 2, 3, 5 的倍數在 ugly 之中的索引值
while len(ugly) < 1500:
    # 更新 i, j, k，直到對應的數位分別乘以 2, 3, 5 大於 ugly 最後一項為止
    while ugly[i]*2 <= ugly[-1]: i += 1
    while ugly[j]*3 <= ugly[-1]: j += 1
    while ugly[k]*5 <= ugly[-1]: k += 1
    ugly.append(min(ugly[i]*2, ugly[j]*3, ugly[k]*5))  # 取最小一項加到 ugly
print(f"The 1500'th ugly number is {ugly[-1]:d}.")

C++ 程式碼

使用時間約為 0 ms，記憶體約為 2.9 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> ugly = {1};
    int i = 0, j = 0, k = 0;
    while(ugly.size() < 1500) {
        while(ugly[i]*2 <= ugly.back()) i++;
        while(ugly[j]*3 <= ugly.back()) j++;
        while(ugly[k]*5 <= ugly.back()) k++;
        ugly.push_back(min(ugly[i]*2, min(ugly[j]*3, ugly[k]*5)));
    }
    printf("The 1500'th ugly number is %d.\n", ugly.back());
    return 0;
}