264. 醜數 II
文章目錄
- 題目描述
- 方法一：暴力法
- 方法二：最小堆
- 方法三：動态規劃
題目描述
給你一個整數 n ，請你找出并傳回第 n 個 醜數 。
醜數 就是隻包含質因數 2、3 和/或 5 的正整數。
示例 1：
輸入：n = 10
輸出：12 解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個醜數組成的序列。
示例 2：
輸入：n = 1
輸出：1
解釋：1 通常被視為醜數。
提示：
1 <= n <= 1690
方法一：暴力法
//連暴力法都沒看懂
//暴力法
class Solution{
public:
int nthUglyNumber(int n){
vector<int> v;
for(long long a=1;a<=INT_MAX;a=a*2)
for(long long b=a;b<=INT_MAX;b=b*3)
for(long long c=b;c<=INT_MAX;c=c*5)
v.push_back(c);
sort(v.begin(),v.end());
return v.at(n-1);
}
};
方法二：最小堆
要得到從小到大的第 nn 個醜數，可以使用最小堆實作。
初始時堆為空。首先将最小的醜數 11 加入堆。
每次取出堆頂元素 x，則 x 是堆中最小的醜數，由于 2x, 3x, 5x 也是醜數，是以将 2x, 3x, 5x 加入堆。
上述做法會導緻堆中出現重複元素的情況。為了避免重複元素，可以使用哈希集合去重，避免相同元素多次加入堆。
在排除重複元素的情況下，第 n 次從最小堆中取出的元素即為第 n 個醜數。
C++代碼
//既然priority_queue是隊列，那麼先要包含頭檔案#include <queue>
//priority_queue和queue不同的就在于我們可以自定義其中資料的優先級, 讓優先級高的排在隊列前面,優先出隊
class Solution
{
public:
int nthUglyNumber(int n)
{
vector<int> factors = { 2,3,5 };
unordered_set<long> seen;//unorder版本的map和set隻提供前向疊代器 在一個unordered_set内部，元素不會按任何順序排序，而是通過元素值的hash值将元素分組放置到各個槽(Bucker，也可以譯為“桶”），這樣就能通過元素值快速通路各個對應的元素（均攤耗時為O（1））。
//priority_queue<Type, Container, Functional>//Functional是仿函數
priority_queue<long, vector<long>, greater<long>> heap;//greater<long>表明是一個升序隊列，小頂堆。//隊列也是堆
seen.insert(1L);//堆//1L表明插入的1是long類型的。//1是醜數，提前插入unodered_set中
heap.push(1L);//堆
int ugly = 0;
for (int i = 0; i < n; i++)
{
long curr = heap.top();//heap是先進先出，每次取出堆頂元素x，則x是堆中最小的醜數
heap.pop();
ugly = (int)curr;//long->int
for (int factor : factors)
{
long next = curr*factor;//有且僅有醜數的 2x,3x,5x 是醜數，是以将 2x,3x,5x 加入堆。
//unodered_set去除第二次出現的數
if (!seen.count(next))//unordered_set::count()函數是C++ STL中的内置函數，用于對unordered_set容器中特定元素的出現進行計數。由于unordered_set容器不允許存儲重複的元素，是以該功能通常用于檢查容器中是否存在元素。如果元素存在于容器中，則該函數傳回1，否則傳回0。
{
seen.insert(next);
heap.push(next);//push(const T& obj)：将obj的副本放到容器的适當位置，這通常會包含一個排序操作。這也是priority_queue與普通queue的差別。
}
}
}
return ugly;
}
};
上述代碼的關鍵點有且僅有醜數的 2x,3x,5x 是醜數，是以将醜數的 2x,3x,5x 加入堆（x代表倍數）。
是以由已知的的醜數可以推導出所有醜數，從小到大的醜數的2x,3x,5x必定是醜數，但是這中間會有重複的數，是以要用unordered_set去重。
時間複雜度：O(nlogn)。得到第 n 個醜數需要進行 n 次循環，每次循環都要從最小堆中取出 1 個元素以及向最小堆中加入最多 3 個元素，是以每次循環的時間複雜度是O(logn+log3n)=O(logn)，總時間複雜度是 O(nlogn)。
空間複雜度：O(n)。空間複雜度主要取決于最小堆和哈希集合的大小，最小堆和哈希集合的大小都不會超過 3n。
方法三：動态規劃
//似懂非懂
方法二使用最小堆，會預先存儲較多的醜數，導緻空間複雜度較高，維護最小堆的過程也導緻時間複雜度較高。可以使用動态規劃的方法進行優化。
我們先模拟手寫醜數的過程
1 打頭，1 乘 2 1 乘 3 1 乘 5，現在是 {1,2,3,5}
輪到 2，2 乘 2 2 乘 3 2 乘 5，現在是 {1,2,3,4,5,6,10}
手寫的過程和采用小頂堆的方法很像，但是怎麼做到提前排序呢
小頂堆的方法是先存再排，dp 的方法則是先排再存
我們設 3 個指針 p2,p3,p5代表的是第幾個數的2倍、第幾個數 3 倍、第幾個數 5 倍
動态方程 dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)
小頂堆是一個元素出來然後存 3 個元素
動态規劃則是辨別 3 個元素，通過比較他們的 2 倍、3 倍、5 倍的大小，來一個一個存
class Solution
{
public:
int nthUglyNumber(int n)
{
vector<int> dp(n + 1);
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= n; i++)
{
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = min(min(num2, num3), num5);
if (dp[i] == num2)
{
p2++;
}
if (dp[i] == num3)
{
p3++;
}
if (dp[i] == num5)
{
p5++;
}
}
return dp[n];
}
};
複雜度分析
時間複雜度：O(n)。需要計算數組 dp 中的 n 個元素，每個元素的計算都可以在 O(1) 的時間内完成。
空間複雜度：O(n)。空間複雜度主要取決于數組 dp 的大小。