2019-08-04-算法-丑数

定义：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。

求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。

1，一遍遍历法-效率比较低

• 如果一个数能够被2整除，那么让他继续除以2；

• 如果一个数能够被3整除，那么让他继续除以3；

• 如果一个数能够被5整除，那么让他继续除以5；

• 如果最后这个数变为1，那么这个数就是丑数，否则不是。

--

public static int getUglyNumber(int index) {
    int number = 0;
    for (int i = 0; i < index; i++) {
        if(isUgly(i)) {
            number = i;
            break;
        }
    }
    return number;
}

public static boolean isUgly(int number) {
    while (number % 2 == 0) {
        number = number / 2;
    }
    while (number % 3 == 0) {
        number = number / 3;
    }
    while (number % 5 == 0) {
        number = number / 5;
    }
    return number == 1;
}

2，空间换时间法：时间效率较高

• 根据丑数的定义，我们可以知道丑数可以由另外一个丑数乘以2，3或者5得到。
• 因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2，3或者5得到的。