LeetCode264 丑数II

发表于 | 分类于 |
字数统计: 1.3k | 阅读时长 ≈ 5

链接： https://leetcode.cn/problems/ugly-number-ii/

题面

给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 或 5 的正整数。

解法

这道题有两种不同的解法，比较容易想到是用一个优先队列
每次取出最小的数分别乘以2、3 和 5 再加入队列
直到取到第 n 个

还有一种dp的解法，这里贴一个在题解中看到的比较好的解释
例如 n = 10， primes = [2, 3, 5]。 打印出丑数列表：1, 2, 3, 4, 5, 6, 8, 9, 10, 12
首先一定要知道，后面的丑数一定由前面的丑数乘以2，或者乘以3，或者乘以5得来。例如，8,9,10,12一定是1, 2, 3, 4, 5, 6乘以2,3,5三个质数中的某一个得到。

这样的话我们的解题思路就是：从第一个丑数开始，一个个数丑数，并确保数出来的丑数是递增的，直到数到第n个丑数，得到答案。那么问题就是如何递增地数丑数？

观察上面的例子，假如我们用1, 2, 3, 4, 5, 6去形成后面的丑数，我们可以将1, 2, 3, 4, 5, 6分别乘以2, 3, 5，这样得到一共6*3=18个新丑数。也就是说1, 2, 3, 4, 5, 6中的每一个丑数都有一次机会与2相乘，一次机会与3相乘，一次机会与5相乘，来得到更大的一个丑数。一共有18次机会形成18个新丑数。

这样就可以用三个指针，

1
2
3
pointer2, 指向1, 2, 3, 4, 5, 6中，还没使用乘2机会的丑数的位置。该指针的前一位已经使用完了乘以2的机会。
pointer3, 指向1, 2, 3, 4, 5, 6中，还没使用乘3机会的丑数的位置。该指针的前一位已经使用完了乘以3的机会。
pointer5, 指向1, 2, 3, 4, 5, 6中，还没使用乘5机会的丑数的位置。该指针的前一位已经使用完了乘以5的机会。

下一次寻找丑数时，则对这三个位置分别尝试使用一次乘2机会，乘3机会，乘5机会，看看哪个最小，最小的那个就是下一个丑数。最后，那个得到下一个丑数的指针位置加一，因为它对应的那次乘法使用完了。

这里需要注意下去重的问题，如果某次寻找丑数，找到了下一个丑数10，则pointer2和pointer5都需要加一，因为5乘2等于10， 2乘5也等于10，这样可以确保10只被数一次。
很巧妙的解法，同时也降低了时间复杂度，在后续更复杂的找丑数问题中也可以进行推广

题解中看到的解释：
官方题解里提到的三个指针p2，p3，p5，但是没有说明其含义，实际上pi的含义是有资格同i相乘的最小丑数的位置。这里资格指的是：如果一个丑数nums[pi]通过乘以i可以得到下一个丑数，那么这个丑数nums[pi]就永远失去了同i相乘的资格（没有必要再乘了），我们把pi++让nums[pi]指向下一个丑数即可。

不懂的话举例说明：

一开始，丑数只有{1}，1可以同2，3，5相乘，取最小的1×2=2添加到丑数序列中。

现在丑数中有{1，2}，在上一步中，1已经同2相乘过了，所以今后没必要再比较1×2了，我们说1失去了同2相乘的资格。

现在1有与3，5相乘的资格，2有与2，3，5相乘的资格，但是2×3和2×5是没必要比较的，因为有比它更小的1可以同3，5相乘，所以我们只需要比较1×3，1×5，2×2。

依此类推，每次我们都分别比较有资格同2，3，5相乘的最小丑数，选择最小的那个作为下一个丑数，假设选择到的这个丑数是同i（i=2，3，5）相乘得到的，所以它失去了同i相乘的资格，把对应的pi++，让pi指向下一个丑数即可。

代码

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<double, vector<double>, greater<double>> pq;
        double a = 1;
        int cnt = 0;
        pq.push(1);
        while(cnt < n) {
            a = pq.top();
            while(pq.size() && pq.top() == a) {
                pq.pop();
            }
            pq.push(a * 2);
            pq.push(a * 3);
            pq.push(a * 5);
            cnt++;
        }
        return a;

    }
};

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int nthUglyNumber(int n) {
        int p1 = 1, p2 = 1, p3 = 1;
        vector<int> dp(n + 1);
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int temp = min(dp[p1] * 2, dp[p2] * 3);
            temp = min(temp, dp[p3] * 5);
            dp[i] = temp;
            if (temp == dp[p1] * 2) {
                p1++;
            }
            if (temp == dp[p2] * 3) {
                p2++;
            }
            if (temp == dp[p3] * 5) {
                p3++;
            }
        } 
        return dp[n];
    }
};