首页 > 代码库 > 剑指offer (34) 丑数

剑指offer (34) 丑数

2024-07-09 14:09:00   217人阅读

题目：只包含因子2，3，5的数成为 丑数

求从小到大第1500个丑数

通常我们把1当作第一个丑数

 

方法一：逐个判断每个整数是不是丑数

如何判断一个数是不是丑数？ 根据定义，丑数只能被2，3，5整除，也就是说，这个数的因子中只能是2，3，5

我们不断用这个数除以2，3，5，直到最后，如果得到1，那么这个数就是丑数

bool IsUgly(int num){    assert(num >= 0);    while (num % 2 == 0) {        num /= 2;    }        while (num % 3 == 0) {        num /= 3;    }        while (num % 5 == 0) {        num /= 5;    }        return (num == 1) ? true : false;}

 

接下来，只需要按照顺序来判断每一个整数是不是丑数

 

方法二：

前面一种方法效率低，因为它需要对每个数都进行判断是不是丑数，对于非丑数，花费了许多时间

根据丑数的定义：丑数的因子只能有2，3，5，可以得知 较大丑数除以较小丑数的结果只能是2，3，5的乘积，即相除结果也是丑数

 

我们可以创建一个数组，里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的

这种思路的关键在于怎样确保数组里面的丑数是排好序的

给定前k个丑数(U1,U2,U3,…,Uk)，计算第k+1个丑数Uk+1

第k+1个丑数肯定是前面k个丑数中的某个数乘以2,3,5的一个结果，

在前k个丑数中，分别找到最小的丑数p2,p3,p5，使得p2*2>Uk；p3*3>Uk；p5*5>Uk，之后Uk+1=min(p2*2, p3*3, p5*5)

注意：因为当前丑数均排好序，所以下一次寻找p2，p3，p5并不需要从头开始，只需要从上一次的p2,p3,p5开始即可

long long KthUgly(int kth) {    assert(kth >= 1);    std::vector<long long> ugly(kth, 0);    int index2 = 0;    int index3 = 0;    int index5 = 0;        ugly.at(0) = 1;    int lastIndex = 0;    while (lastIndex + 1 != kth) {        while (ugly.at(index2) * 2 <= ugly.at(lastIndex)) {            ++index2;        }                while (ugly.at(index3) * 3 <= ugly.at(lastIndex)) {            ++index3;        }                while (ugly.at(index5) * 5 <= ugly.at(lastIndex)) {            ++index5;        }                long long min = std::min(std::min(ugly.at(index2) * 2, ugly.at(index3) * 3), ugly.at(index5) * 5);        ++lastIndex;        ugly.at(lastIndex) = min;    }    return ugly.at(lastIndex);}

 

 


联系
我们