C++找出第n个丑数两种方式：简单方式和动态规划

丑数是只有2、3或5是质因数的数字，序列1、2、3、4、5、6、8、9、10、12、15……显示前11个丑数，按照惯例，包含1。

给定一个数字n，任务是找出第n个丑数。

例子：

输入  : n = 7
输出 : 8

输入  : n = 10
输出 : 12

输入  : n = 15
输出 : 24

输入  : n = 150
输出 : 5832

方法1(简单的)

循环所有正整数，直到丑数计数小于n，如果一个整数是丑数，则增加丑数计数。

要检查一个数是不是丑的，把这个数除以2、3和5的最大可除幂，如果这个数变成1，那么它就是丑数，否则不是。

例如，让我们看看如何检查300是否是丑数，2的最大可除指数是4，300除以4等于75。3的最大可除数是3，75除以3等于25。5的最大可除指数是25，25除以25等于1。因为最后得到1，所以300是个丑数。

C++实现：

// CPP程序找出第n个丑数 
# include<stdio.h> 
# include<stdlib.h> 
  
/*这个函数把a除以b的最大可除幂*/
int maxDivide(int a, int b) 
{ 
  while (a%b == 0) 
   a = a/b;  
  return a; 
}     
  
/* 函数的作用是检查一个数字是否是丑数 */
int isUgly(int no) 
{ 
  no = maxDivide(no, 2); 
  no = maxDivide(no, 3); 
  no = maxDivide(no, 5); 
    
  return (no == 1)? 1 : 0; 
}     
  
/* 函数可以得到第n个丑数*/
int getNthUglyNo(int n) 
{ 
  int i = 1;  
  int count = 1;   /* 丑数总数 */ 
  
  /*检查所有整数，直到丑数总数变成n */ 
  while (n > count) 
  { 
    i++;       
    if (isUgly(i)) 
      count++;  
  } 
  return i; 
} 
  
/* 测试程序 */
int main() 
{ 
    unsigned no = getNthUglyNo(150); 
    printf("第150个丑数是 %d ",  no); 
    getchar(); 
    return 0; 
} 

这种方法的时间效率不高，因为它检查所有整数，直到丑数计数变成n，但是这种方法的空间复杂度是O(1)。

方法2(使用动态规划)

这是一个有额外空间O(n)的高效时间解决方案，假设丑数序列是1、2、3、4、5、6、8、9、10、12、15……

因为每个数只能被2、3、5整除，所以看序列的一种方法是把序列分成以下三组：

(1) 1×2,2×2,3×2,4×2,5×2，…

(2) 1×3,2×3,3×3,4×3,5×3，…

(3) 1×5,2×5,3×5,4×5,5×5，…

我们可以发现每个子序列都是丑序列本身(1,2,3,4,5，…)乘以2,3,5。然后利用类似于归并排序的方法，求出三个子序列中所有的丑数。我们每走一步都选择最小的一步，然后再往前走一步。

1、为一个丑数声明一个数组：ugly[n]
2、初始化第一个丑数: ugly[0] = 1
3、初始化三个数组索引变量i2, i3, i5指向
丑数组的第一个元素：
i2 = i3 = i5 =0;
4、初始化3个选项为下一个丑数:
next_mulitple_of_2 =ugly(i2) * 2;
next_mulitple_of_3 =ugly(i3) * 3
next_mulitple_of_5 =ugly(i5) * 5;
5、现在循环填入所有丑数直到150:
For (i = 1; i < 150; i++ ) 
{
    /* 这些小步骤没有经过优化以获得良好的可读性，可在实现中进行优化 */
    next_ugly_no  = Min(next_mulitple_of_2,
                        next_mulitple_of_3,
                        next_mulitple_of_5); 

    ugly[i] =  next_ugly_no       

    if (next_ugly_no  == next_mulitple_of_2) 
    {             
        i2 = i2 + 1;        
        next_mulitple_of_2 = ugly[i2]*2;
    } 
    if (next_ugly_no  == next_mulitple_of_3) 
    {             
        i3 = i3 + 1;        
        next_mulitple_of_3 = ugly[i3]*3;
     }            
     if (next_ugly_no  == next_mulitple_of_5)
     {    
        i5 = i5 + 1;        
        next_mulitple_of_5 = ugly[i5]*5;
     } 
     
}/* 循环结束 */ 
6.返回下一个丑数

例子：

让我们看看它是如何工作的

初始化
   ugly[] =  | 1 |
   i2 =  i3 = i5 = 0;

第1次迭代
   ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
            = Min(2, 3, 5)
            = 2
   ugly[] =  | 1 | 2 |
   i2 = 1,  i3 = i5 = 0  (i2增加了) 

第二次迭代
    ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 3, 5)
             = 3
    ugly[] =  | 1 | 2 | 3 |
    i2 = 1,  i3 =  1, i5 = 0  (i3增加了 ) 

第三次迭代
    ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 6, 5)
             = 4
    ugly[] =  | 1 | 2 | 3 |  4 |
    i2 = 2,  i3 =  1, i5 = 0  (i2增加了)

第四次迭代
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 5)
              = 5
    ugly[] =  | 1 | 2 | 3 |  4 | 5 |
    i2 = 2,  i3 =  1, i5 = 1  (i5增加了 )

第五次迭代
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 10)
              = 6
    ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |
    i2 = 3,  i3 =  2, i5 = 1  (i2和i3增加了)

继续同样的方式直到 I < 150

动态规划C++实现：

// c++程序找出第n个丑数 
# include<bits/stdc++.h> 
using namespace std; 
  
/* 函数可以得到第n个丑数*/
unsigned getNthUglyNo(unsigned n) 
{ 
    unsigned ugly[n]; // 存储丑数 
    unsigned i2 = 0, i3 = 0, i5 = 0; 
    unsigned next_multiple_of_2 = 2; 
    unsigned next_multiple_of_3 = 3; 
    unsigned next_multiple_of_5 = 5; 
    unsigned next_ugly_no = 1; 
  
    ugly[0] = 1; 
    for (int i=1; i<n; i++) 
    { 
       next_ugly_no = min(next_multiple_of_2, 
                           min(next_multiple_of_3, 
                               next_multiple_of_5)); 
       ugly[i] = next_ugly_no; 
       if (next_ugly_no == next_multiple_of_2) 
       { 
           i2 = i2+1; 
           next_multiple_of_2 = ugly[i2]*2; 
       } 
       if (next_ugly_no == next_multiple_of_3) 
       { 
           i3 = i3+1; 
           next_multiple_of_3 = ugly[i3]*3; 
       } 
       if (next_ugly_no == next_multiple_of_5) 
       { 
           i5 = i5+1; 
           next_multiple_of_5 = ugly[i5]*5; 
       } 
    } /*循环结束 (i=1; i<n; i++) */
    return next_ugly_no; 
} 
  
/* 驱动程序测试以上功能 */
int main() 
{ 
    int n = 150; 
    cout << getNthUglyNo(n); 
    return 0; 
} 

时间复杂度：O(n)

辅助空间：O(n)