264 丑数II
思路
借鉴合并k个有序链表思路,将丑数分为三条链表:2的倍数,3的倍数,5个倍数
如下:
能被 2 整除的丑数:
能被 3 整除的丑数:
能被 5 整除的丑数:
我们如果把这三条「有序链表」合并在一起并去重,得到的就是丑数的序列,其中第 n 个元素就是题目想要的答案:
问题在于如何给丑数「排序」和「去重」
最直接的方法:
- 小根堆:给丑数排序
- 哈希表:给丑数去重
class Solution {
public:
int nthUglyNumber(int n) {
// 给丑数排序,小根堆
priority_queue<long, vector<long>, greater<long>> heap;
// 给丑数去重
unordered_set<long> hashMap;
// 质因子
vector<int> factor = {2, 3, 5};
// 初始化
hashMap.insert(1L);
heap.push(1L);
int ugly = 0;
while(n--){
long cur = heap.top();
heap.pop();
ugly = (int)cur;
for(int fac : factor){
long num = cur * fac;
if(!hashMap.count(num)){
hashMap.insert(num);
heap.push(num);
}
}
}
return ugly;
}
};
复杂度分析
- 时间复杂度:\(O(nlogn)\)。 得到第 n 个丑数需要进行 n 次循环,每次循环都要从最小堆中取出 1 个元素以及向最小堆中加入最多 3 个元素,因此每次循环的时间复杂度是 \(O(log(3n)+3log(3n))=O(logn)\),总时间复杂度是 \(O(nlogn)\)。
- 空间复杂度:\(O(n)\)。 空间复杂度主要取决于最小堆和哈希集合的大小,最小堆和哈希集合的大小都不会超过 3n。
「如何排序」:
- 维护三个指针p2,p3,p5分别指向三条有序链表的链表头,每次取三条有序链表的链表头进行比较,取最小值插入到丑数数组中。
- 在这次比较中,两个非最小值会参与到下次的比较中,通过自增最小值对应的指针,将最小值对应的链表头更新,使其在下次比较中的值变大。
通过这种方法,最后的结果集一定是从小到大的。
「如何去重」:
在「最小堆+哈希表」的解法中,每个丑数都分别乘2,3,5所以导致重复,那么避免重复的方法就是防止每个丑数都乘2,3,5
如何做到呢?一开始丑数只有{1},它有与2,3,5相乘的资格。
- 第一次比较中,我们选出了最小的2,得到了第二个丑数1 * 2
- 第二次比较,丑数中有{1,2}
- 如果将1和2分别与2,3,5相乘,那么会得到第一个重复的1 * 2。我们仔细想想为什么会出现这个重复的数字,是因为丑数中已经存在1 * 2,是我们上一次比较中计算得到的丑数。为了去掉1 * 2,我们一定不能让1与2两次相乘,也就是说:1失去了与2相乘的资格,表现为p2 != 1。
- 在本次比较中,我们比较的数字有{1 * 3, 1 * 5, 2 * 2, 2 * 3, 2 * 5},但是实际比较的数字为{1 * 3, 1 * 5, 2 * 2}。这里出现第二个问题:为什么2 * 3和2 * 5不参与实际的比较? 这时因为有比2 * 3和2 * 5更小的1 * 3和1 * 5,看起来有点像废话,但是仔细想想,这是因为1还没有失去与3和5相乘的资格
从以上分析中,我们可以得出一个结论:
- 丑数nums[\(p_i\)]为有资格同i相乘的最小丑数,指针\(p_i\)表示对应的最小位置
- \(p_i\)的自增起到了「去重」和「不漏」的双重作用。
- 「去重」 去重依赖于两个操作,指针自增和3个if。
- 指针自增:第一次1 * 2后,p2++导致了1不能够再乘2,丑数中无法再出现1 * 2。
- 3个if:假如一个数既可通过2得到又可以通过3得到,此时必然会重复计算并重复加入到数组,因此此时需要既迭代2对应的下标p2,也迭代3对应的下标p3,所以if如果换成if-else,必然会有大量重复值出现
- 「不漏」:因为维护了3个指针,每个指针都有机会自增,因此每个丑数都有一次与2,3,5相乘的机会
- 「去重」 去重依赖于两个操作,指针自增和3个if。
换种视角:
- 「不重」:nums[pi] * i 中的最小值大于之前生成的所有丑数,因为之前的数都是 i 与 比 nums[pi] 更小的数生成的
- 「不漏」:nums[pi] * i中的最小值是后续丑数中最小的,因为比 nums[pi] 小的数都乘过,比 nums[pi] 大的数肯定大
class Solution {
public:
int nthUglyNumber(int n) {
int list2 = 1, list3 = 1, list5 = 1;
int p2 = 1, p3 = 1, p5 = 1;
int p = 1;
vector<int> ugly(n + 1);
while(p <= n){
int m = min(list2, min(list3, list5));
ugly[p] = m;
p++;
if(m == list2){
list2 = 2 * ugly[p2];
p2++;
}
if(m == list3){
list3 = 3 * ugly[p3];
p3++;
}
if(m == list5){
list5 = 5 * ugly[p5];
p5++;
}
}
return ugly[n];
}
};