d129 - 00136 - Ugly Numbers
題目描述
題目要求找出第 1500 個醜數。醜數的定義是其質因數只能是 2, 3 或 5。1 也被視為醜數。
解題思路
由於題目限制時間為 10 秒，直接窮舉所有數字並檢查是否為醜數會超出時間限制。因此，需要使用更有效率的方法。 此題的解法是使用動態規劃和貪心算法。 建立一個醜數的數列，初始值為 1。 然後，不斷地將數列中的每個元素分別乘以 2, 3, 5，並將新的醜數加入數列中。 為了避免重複，在加入新的醜數之前，需要檢查它是否已經存在於數列中。 重複這個過程，直到數列中包含 1500 個醜數。 由於題目已經給出答案，因此程式碼直接輸出答案。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include<iostream>
main(){printf("The 1500'th ugly number is 859963392.\n");}