题目描述

我们把只包含质因子2、3和5的数称作丑数（Ugly Number）。

例如6、8都是丑数，但14不是，因为它包含质因子7。

求第n个丑数的值。

样例

输入：5

输出：5

算法1

(小根堆、set)

1. 使用数据结构set来存储每个元素是否出现过，没有就加入堆中
2. 小根堆会自动排序，将整个输入变成一个升序排列的序列。

时间复杂度

$O(nlogn)$
while循环一共会执行n次，每次执行最多往堆中插入3n个元素，插入一次元素时间复杂度是O(logn)，所以是$O(nlogn)$。

C++ 代码

class Solution {
public:
    int getUglyNumber(int n) {
        unordered_set<int> se;
        priority_queue<int, vector<int>, greater<int>> minheap;

        se.insert(1);
        minheap.push(1);

        int cnt = 1;

        while(cnt < n)
        {
            int t = minheap.top();
            minheap.pop();

            if(!se.count(t * 2))
            {
                se.insert(t * 2);
                minheap.push(t * 2);
            }

            if(!se.count(t * 3))
            {
                se.insert(t * 3);
                minheap.push(t * 3);
            }

            if(!se.count(t * 5))
            {
                se.insert(t * 5);
                minheap.push(t * 5);
            }

            cnt ++;
        }

        return minheap.top();
    }
};

算法2

(三路归并)

1. 三指针的思想，所以定义3个指针i, j, k。
2. vector存储的是丑数数组，一开始只有1个1，后面 动态添加元素进vector。
3. t取出的是3个指针分别指向的3个子数组(2 3 5)中的最小值。如果最小值是3个子数组中的哪一个，就把里面的指针i j k 增1。因为可能同时出现在多个数组，所以用3个if来表示。
4. 最后输出vector的最后一位，就是第n个丑数。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> res(1, 1);

        int i = 0, j = 0, k = 0;
        while(res.size() < n)
        {
            int t = min(res[i] * 2, min(res[j] * 3, res[k] * 5));
            res.push_back(t);

            if(res[i] * 2 == t) i ++;
            if(res[j] * 3 == t) j ++;
            if(res[k] * 5 == t) k ++;
        }

        return res.back();
    }
};