跳转至

264 丑数II

leetcode

思路

借鉴合并k个有序链表思路,将丑数分为三条链表:2的倍数,3的倍数,5个倍数

如下:

能被 2 整除的丑数:

1*2 -> 2*2 -> 3*2 -> 4*2 -> 5*2 -> 6*2 -> 8*2 ->...

能被 3 整除的丑数:

1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 8*3 ->...

能被 5 整除的丑数:

1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 8*5 ->...

我们如果把这三条「有序链表」合并在一起并去重,得到的就是丑数的序列,其中第 n 个元素就是题目想要的答案:

1 -> 1*2 -> 1*3 -> 2*2 -> 1*5 -> 3*2 -> 4*2 ->...

问题在于如何给丑数「排序」和「去重」

最直接的方法:

  • 小根堆:给丑数排序
  • 哈希表:给丑数去重
    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。

「如何排序」:

  1. 维护三个指针p2,p3,p5分别指向三条有序链表的链表头,每次取三条有序链表的链表头进行比较,取最小值插入到丑数数组中。
  2. 在这次比较中,两个非最小值会参与到下次的比较中,通过自增最小值对应的指针,将最小值对应的链表头更新,使其在下次比较中的值变大。

通过这种方法,最后的结果集一定是从小到大的。

「如何去重」:

在「最小堆+哈希表」的解法中,每个丑数都分别乘2,3,5所以导致重复,那么避免重复的方法就是防止每个丑数都乘2,3,5

如何做到呢?一开始丑数只有{1},它有与2,3,5相乘的资格。

  1. 第一次比较中,我们选出了最小的2,得到了第二个丑数1 * 2
  2. 第二次比较,丑数中有{1,2}
    1. 如果将1和2分别与2,3,5相乘,那么会得到第一个重复的1 * 2。我们仔细想想为什么会出现这个重复的数字,是因为丑数中已经存在1 * 2,是我们上一次比较中计算得到的丑数。为了去掉1 * 2,我们一定不能让1与2两次相乘,也就是说:1失去了与2相乘的资格,表现为p2 != 1。
    2. 在本次比较中,我们比较的数字有{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相乘的机会

换种视角:

  • 「不重」: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];
    }
};