Blog Content

Lintcode-4:丑数 II

每日一练 算法 C/C++ LintCode   2010-03-04 22:12:04

---

描述
设计一个算法，找出只含素因子2，3，5 的第 n 小的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

我们可以认为1也是一个丑数
 
样例
如果n = 9， 返回 10

挑战
要求时间复杂度为O(nlogn)或者O(n)

什么是丑数呢？丑数就是只包含因子2，3，5的数称作是丑数，在这里这种定义我是比较模糊的，所以上网查找了更加浅显的定义，丑数就是另一个丑数乘以2，3，5以后的结果（1除外，通常认为1是最小的丑数）。

直接寻找丑数，由丑数的定义可知，任何一个丑数都是2^i * 3^j * 5^m这种形式的，因此不断寻找丑数，将他们按从小到大的顺序进行排列，直到第n个即为结果。

首先定义一个数组存放丑数，认为1是丑数，则初始化数组num[0] = 1，然后从2,3,5这三个种子中挑选，选择num[0]*2，num[0]*3，num[0]*5中最小的数为新的丑数，显然应该选择2，即num[1] = 2，然后在从2,3,5中选择，这时应该是从num[1]*2，num[0]*3，num[0]*5中进行选择，显然选择3，即num[2] = 3，然后再从num[1]*2，num[1]*3，num[0]*5中选择最小的，选择2，即num[3] = 4，依次进行如下操作，得到最终的结果。

/*
* 找到第N个丑数。丑数就是只包含因子2，3，5的数称作是丑数，在这里这种定义我是比较模糊的，所以上网查找了更加浅显的定义，丑数就是另一个丑数乘以2，3，5以后的结果（1除外，通常认为1是最小的丑数）。
*/

#include 

int min(int a, int b, int c)       
{       
    int temp = (a < b ? a : b);       
    return (temp < c ? temp : c);       
}   

int nthUglyNumber(int n) {  
    // write your code here  
    //int *ugly = new int[n];  
    int ugly[n];
    ugly[0] = 1;  
    int num_2 = 0;  
    int num_3 = 0;  
    int num_5 = 0;  
    for(int i = 1;i

输出结果：
10
       

              上一篇：Lintcode-3:统计数字 
              

       下一篇：Lintcode-5:在数组中找到第k大的元素