剑指 Offer 49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

动态合并数组——动态规划

思路

丑数的排列
假设当前存在 3 个数组 nums2, nums3, nums5 分别代表丑数序列从 1 开始分别乘以 2, 3, 5 的序列， 即

nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
//显然抽数序列为上述序列的merge

那么， 最终的丑数序列实际上就是这 3 个有序序列对的合并结果， 计算丑数序列也就是相当于 合并 3 个有序序列。

算法

1. 设置i,j,k三个指针分别指向上述序列对应处。
2. 合并上述序列直到满足n

   实现

   int nthUglyNumber(int n) {
    vector<int> dp(n,0);
    dp[0]=1;
    int i=0,j=0,k=0;
    //合并三个有序序列
    for(int p=1;p<n;p++){
        int vi=2*dp[i],vj=3*dp[j],vk=5*dp[k];
        int minV=min(min(vi,vj),vk);
        dp[p]=minV;
        //重复元素便跳过。
        i+=vi==minV;
        j+=vj==minV;
        k+=vk==minV;
    }
    return dp.back();
   }

   复杂度分析

• 时间复杂度:
• 空间复杂度:

算法2

思路

算法

实现

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分