方法一:堆
class Solution {
public:int nthUglyNumber(int n) {vector<int> factors = {2, 3, 5};unordered_set<long> seen;priority_queue<long, vector<long>, greater<long>> heap;seen.insert(1L);heap.push(1L);int ugly = 0;for(int i = 0; i < n; i++){long curr = heap.top();heap.pop();ugly = (int)curr;for(int factor : factors){long next = curr * factor;if(!seen.count(next)){seen.insert(next);heap.push(next);}}}return ugly;}
};
时间复杂度:O(nlogn)。得到第 n 个丑数需要进行 n 次循环,每次循环都要从最小堆中取出 1 个元素以及向最小堆中加入最多 3 个元素,因此每次循环的时间复杂度是 O(log(3n)+3log(3n))=O(logn),总时间复杂度是 O(nlogn)。
空间复杂度:O(n)。空间复杂度主要取决于最小堆和哈希集合的大小,最小堆和哈希集合的大小都不会超过 3n。
我们可以使用堆来模拟丑数的情况,我们定义一个堆,堆顶是最小的数,这个时候我们让堆顶的数乘以factors的三个不同因子的情况,继续加入到堆中,然后将堆顶元素弹出,这个时候堆顶元素就是第二小的数(包含已弹出的最小数),也就是第二个丑数,然后不断继续将堆顶元素乘以factors中顶三个不同因子,得到更多丑数。由于我们遍历了n次,要遍历第n次的时候,前面已经弹出了n-1个丑数,那么第n个数就是第n个丑数。有人可能会问那么有重复的丑数怎么办,那就定义一个哈希集合检查,如果乘以因子后的丑数已经出现在哈希集合中,那么就不会推入到堆里。
方法2:动态规划
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;int num3 = dp[p3] * 3;int 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 的大小。
这个动态规划的思路就是,每一个丑数都可以乘以2、3、5中的某一个因子变成另外一个数,然后由于节省空间,我们用指针来记录将哪一个丑数放在dp哪个位置。
举个例子,dp[1]为1,这时候三个指针都指向1,我们要找dp[2]要放什么呢?这时候有1x2=2, 1x3=3, 1x5=5。这时候我们要将他们正确插入到dp中,这时候就找其中最小的数也就是2放到dp[2]中,dp[2]中放的是1x2。继续找dp[3]要存放什么呢,这个时候有1x3=3, 1x5=5,还有dp[2]乘以2也就是1x2 x 2=4。那么三者中3最小,所以dp[3]中存放的是1x3=3,这个时候令p3++指向2。
通过上面我们可以明白,每一个dp[i]存放的实际上都是从1开始不断乘以某个因子后形成的丑数,如1x2或者1x3或者1x2x2之类的数,而我们要做的,就是将还没计算过的dp[i]乘以各个因子(dp[i]本身就是由许多因子组成)。