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整除，所以看序列的一种方法是把序列分成以下三组：
【C++找出第n个丑数两种方式（简单方式和动态规划）】(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_noif (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)