首页 > 代码库 > 【面试题034】丑数

【面试题034】丑数

2024-07-05 18:10:59   229人阅读

【面试题034】丑数
题目：
    我们把只包含因子2、3和5的数称为丑数(Ugly Number)。
    求按从小到大的顺序的第1500个丑数。
    例如6、8都是丑数，但14不是，因为他包含因子7。习惯上我们把1当做第一个丑数。
 
思路一：
    逐个的判断，效率不高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
  
#include <iostream>

using namespace std;

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

int GetUglyNumber(int index)
{
    if (index <= 0)
    {
        return 0;
    }
    int number = 0;
    int uglyFound = 0;
    while (uglyFound < index)
    {
//number一直在累加，while判断的是uglyFound
        ++number;
        if (IsUgly(number))
        {
            ++uglyFound;
        }
    }
    return number;
}


int main()
{
    cout << GetUglyNumber(15) << endl;
    return 0;
}
 
思路二：
    创建数组保存已经找到的丑数，用空间换时间的解法。
    尝试找一种只计算丑数的方法，而不是在非丑数的整数上花时间，
——根据定义丑数应该是另一个丑数乘以2、3或者5的结果，当然初始化的时候只有1，
    1*2 1*3 1*5
    2*2 3*2 5*2 
    2*3 3*3 5*3
    2*5 3*5 5*5……   
    都分别乘以2、3、5事实上这不是必须的，请看以下代码中
——三个int指针的应用：
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
  
#include <iostream>

using namespace std;


int Min(int number1, int number2, int number3)
{
    int min = (number1 < number2) ? number1 : number2;
    min = (min < number3) ? min : number3;
    return min;
}

int GetUglyNumber(int index)
{
    if (index <= 0)
    {
        return 0;
    }
    int *pUglyNumbers = new int[index];
    pUglyNumbers[0] = 1;
    int nextUglyIndex = 1;

    int *pMultiply2 = pUglyNumbers;
    int *pMultiply3 = pUglyNumbers;
    int *pMultiply5 = pUglyNumbers;

    while (nextUglyIndex < index)
    {
        int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);
        pUglyNumbers[nextUglyIndex] = min;

        while (*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
        {
            ++pMultiply2;
        }
        while (*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
        {
            ++pMultiply3;
        }
        while (*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
        {
            ++pMultiply5;
        }
        ++nextUglyIndex;
    }
    int ugly = pUglyNumbers[nextUglyIndex - 1];
    delete[] pUglyNumbers;
    return ugly;
}

int main()
{
    cout << GetUglyNumber(15) << endl;
    return 0;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


联系
我们