剑指offer(C++)-JZ49：丑数(算法-其他)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

数据范围：0≤n≤2000

要求：空间复杂度 O(n)?， 时间复杂度 O(n)

示例：

输入：

7

返回值：

8

解题思路：

本题考察算法思维。两种解题思路：

1)优先队列-最小堆

? ? ? ?丑数是含质因子2、3、5的数，从1开始，1乘这三个因数得到的数就是丑数，以此类推，丑数乘因数也是丑数。考虑到这样操作可能会有重复，所以借助map完成去重。再构建优先队列-小顶堆往里面塞入丑数，放入的过程会自动进行排序，排序复杂度在O(log2n)。

? ? ? ?假设获取前n个丑数，就进行n次循环，每次循环将最小的丑数弹出，并放入新的丑数，放入的时候还需要进行重复性判断。

? ? ? ?综合下来，算法时间复杂度为O(nlog2n)。

2)动态规划

? ? ? ?丑数1 2 3 4 5 6 8 9 10等等，每个丑数一定是前面某个数的235倍数，可结合动态规划思想，设置三个步进下标ijk，将已知丑数依次乘235得到后续丑数，在此过程中还需要确保丑数是从小到大放入容器的，即进行最小值比较。

? ? ? ?为了直观些，简单模拟下前面几步的流程：

1）开始ijk均为0，则从数字1开始，丑数后续依次为2 3 5，其中2最小，则i升为1。

2）i为1，即第二个丑数2，用2的2倍也就是4和3 5比较，此时3最小，则j升为1。

3）i和j为1，即用第二个丑数2的2倍3倍，即4和6，和5比较，此时4最小，则i继续升为2。

4）i为2，j为1，k为0，用3的2倍、2的3倍、1的5倍比较，即6 6 4，此时5最小，则k升为1。

5）i为2，j为1，k为1，用3的2倍、2的3倍，2的5倍比较，即6 6 10，此时6最小，i和j同时升1。

? ? ? ?从上述5步可看到全局规律，ijk是从前往后慢慢推进的，结合了动态规划的思想，后续步进以前面为基准，动态扩展后续丑数

? ? ? ?该算法时间复杂度为O(n)，也是题目理想解法。

测试代码：

1)优先队列-最小堆

#include <queue>
class Solution {
public:
    // 获取丑数
    int GetUglyNumber_Solution(int index) {
        // 判空
        if(index == 0){
            return 0;
        }
        // 定义因数集合
        vector<int> factors = { 2, 3, 5};
        // 定义哈希表
        unordered_map<long, bool> um;
        // 定义优选队列-小顶堆
        priority_queue<long, vector<long>, greater<>> pq;
        // 放入1
        um[long(1)] = true;
        pq.push(long(1));
        long result = 0;
        for(int i = 0; i < index; ++i){
            // 每次取顶，也就是最小值，弹出
            result = pq.top();
            pq.pop();
            for(int j = 0; j < 3; ++j){
                // 存入235倍数的值
                long temp = result * factors[j];
                // 只存放非重复值
                if(um.find(temp) == um.end()){
                    um[temp] = true;
                    pq.push(temp);
                }
            }
        }
        return int(result);
    }
};

2)动态规划

#include <queue>
class Solution {
public:
    // 获取丑数
    int GetUglyNumber_Solution(int index) {
        // 判空
        if(index == 0){
            return 0;
        }
        // 定义丑数集合
        vector<int> uglyNums = { 1 };
        // 循环按规律找到所有丑数
        int i = 0, j = 0, k = 0;
        int t;
        for(t = 0; t < index; ++t){
            // ijk表示已知丑数乘235的进度
            // 举例说明
            // 1）开始ijk均为0，则从数字1开始，丑数后续依次为2 3 5，其中2最小，则i升为1
            // 2）i为1，即第二个丑数2，用2的2倍也就是4和3 5比较，此时3最小，则j升为1
            // 3）i和j为1，即用第二个丑数2的2倍3倍，即4和6，和5比较，此时4最小，则i继续升为2
            // 4）i为2，j为1，k为0，用3的2倍、2的3倍、1的5倍比较，即6 6 4，此时5最小，则k升为1
            // 5）i为2，j为1，k为1，用3的2倍、2的3倍，2的5倍比较，即6 6 10，此时6最小，i和j同时升1
            // 从上述5步可看到全局规律，ijk是从前往后慢慢推进的，结合了动态规划的思想，后续步进以前面为基准，动态扩展后续丑数
            int num2 = uglyNums[i] * 2;
            int num3 = uglyNums[j] * 3;
            int num5 = uglyNums[k] * 5;
            int minNum = min(num2, min(num3, num5));
            uglyNums.push_back(minNum);
            if(minNum == num2){
                i++;
            }
            if(minNum == num3){
                j++;
            }
            if(minNum == num5){
                k++;
            }
        }
        return uglyNums[t - 1];
    }
};