【剑指Offer】丑数

Posted on | In ,

题目

把只包含因子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
public int GetUglyNumber_Solution(int index) {
    if (index < 1)
        return 0;

    int number = 1;
    int currentIdx = 1;

    while (currentIdx < index) {
        if (isUglyNumber(number))
            currentIdx++;

        number++;
    }

    return number;
}

private boolean isUglyNumber(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;
}

创建数组保存已经找到的丑数，用空间换时间的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int GetUglyNumber_Solution(int index) {
    if (index < 1)
        return 0;

    int[] array = new int[index];
    int t2 = 0;
    int t3 = 0;
    int t5 = 0;
    array[0] = 1;

    for (int i = 1; i < index; i++) {
        array[i] = Math.min(array[t2] * 2, Math.min(array[t3] * 3, array[t5] * 5));

        if(array[i] == array[t2] * 2)
            t2++;
        if (array[i] == array[t3] * 3)
            t3++;
        if (array[i] == array[t5] * 5)
            t5++;
    }

    return array[index - 1];
}