[LeetCode] 264. Ugly Number II 丑陋数之二

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10

Output: 12

Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number.
n does not exceed 1690.

Hint:

The naive approach is to call isUgly for every number until you reach the n^th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.
Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

这道题是之前那道 Ugly Number 的拓展，这里让找到第n个丑陋数，还好题目中给了很多提示，基本上相当于告诉我们解法了，根据提示中的信息，丑陋数序列可以拆分为下面3个子列表：

(1) 1x2, 2x2, 2x2, 3x2, 3x2, 4x2, 5x2...

(2) 1x3, 1x3, 2x3, 2x3, 2x3, 3x3, 3x3...

(3) 1x5, 1x5, 1x5, 1x5, 2x5, 2x5, 2x5...

仔细观察上述三个列表，可以发现每个子列表都是一个丑陋数分别乘以 2，3，5，而要求的丑陋数就是从已经生成的序列中取出来的，每次都从三个列表中取出当前最小的那个加入序列，请参见代码如下：

解法一：

class Solution {

public:

    int nthUglyNumber(int n) {

        vector<int> res(, );

        int i2 = , i3 = , i5 = ;

        while (res.size() < n) {

            int m2 = res[i2] * , m3 = res[i3] * , m5 = res[i5] * ;

            int mn = min(m2, min(m3, m5));

            if (mn == m2) ++i2;

            if (mn == m3) ++i3;

            if (mn == m5) ++i5;

            res.push_back(mn);

        }

        return res.back();

    }

};

我们也可以使用最小堆来做，首先放进去一个1，然后从1遍历到n，每次取出堆顶元素，为了确保没有重复数字，进行一次 while 循环，将此时和堆顶元素相同的都取出来，然后分别将这个取出的数字乘以 2，3，5，并分别加入最小堆。这样最终 for 循环退出后，堆顶元素就是所求的第n个丑陋数，参见代码如下：

解法二：

class Solution {

public:

    int nthUglyNumber(int n) {

        priority_queue<long, vector<long>, greater<long>> pq;

        pq.push();

        for (long i = ; i < n; ++i) {

            long t = pq.top(); pq.pop();

            while (!pq.empty() && pq.top() == t) {

                t = pq.top(); pq.pop();

            }

            pq.push(t * );

            pq.push(t * );

            pq.push(t * );

        }

        return pq.top();

    }

};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/264

类似题目：

参考资料：

https://leetcode.com/problems/ugly-number-ii/

https://leetcode.com/problems/ugly-number-ii/discuss/69372/Java-solution-using-PriorityQueue

https://leetcode.com/problems/ugly-number-ii/discuss/69364/My-16ms-C%2B%2B-DP-solution-with-short-explanation

https://leetcode.com/problems/ugly-number-ii/discuss/69368/Elegant-C%2B%2B-Solution-O(N)-space-time-with-detailed-explanation.

LeetCode All in One 题目讲解汇总(持续更新中...)

巴特西

[LeetCode] 264. Ugly Number II 丑陋数之二

最新文章

热门文章