【面试题034】丑数

【面试题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;
}