题目描述

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

题解一

第一种方法是逐个数字判断是不是丑数。

判断某个数字是否为丑数的思想很简单，根据丑数的定义，丑数只能被2、3或5整除。因此不断将这个数字除以2、3或5，如果最后结果为1，则说明这个数是丑数；如果不能被整除，则说明不是丑数。

时间复杂度为O(n^2)，空间复杂度为O(1)。

public int GetUglyNumber_Solution(int index) {
    int count = 0, num = 1;
    while (true){
        if (isUgly(num))
            count++;
        if (count == index)
            return num;
        num++;
    }
}

private boolean isUgly(int num) {
    if (num == 1)
        return true;
    while (num > 1) {
        if (num % 2 == 0) num /= 2;
        else if (num % 3 == 0) num /= 3;
        else if (num % 5 == 0) num /= 5;
        else return false;
    }
    return num == 1;
}

题解二

我们可以创建数组保存已找到的丑数，根据丑数的定义，丑数应该是另一个丑数乘上2、3或5的结果，所以我们用一个数组保存排序好的丑数，每个丑数都是由前面的丑数乘上2、3或5得到的。

为了按序保存丑数，创建三个队列，用于保存丑数分别乘以2、3或5的结果。由于队列先进先出的特性，因此队列中的丑数也是排好序的，所以每次都将三个队列的队头进行比较，将较小值存入数组中，然后再将队头删除。

时间复杂度为O(n)，空间复杂度为O(n)。

public int GetUglyNumber_Solution(int index) {
    if (index == 0)
        return 0;
    Stack<Integer> stack = new Stack<>();
    int min = 1;
    stack.add(min);
    Queue<Integer> queue2 = new LinkedList<>();
    Queue<Integer> queue3 = new LinkedList<>();
    Queue<Integer> queue5 = new LinkedList<>();

    while (stack.size() < index) {
        queue2.offer(min * 2);
        queue3.offer(min * 3);
        queue5.offer(min * 5);

        int val2 = queue2.isEmpty() ? Integer.MAX_VALUE : queue2.peek();
        int val3 = queue3.isEmpty() ? Integer.MAX_VALUE : queue3.peek();
        int val5 = queue5.isEmpty() ? Integer.MAX_VALUE : queue5.peek();

        min = Math.min(Math.min(val2, val3), val5);
        stack.add(min);
        if (min == val2) queue2.poll();
        if (min == val3) queue3.poll();
        if (min == val5) queue5.poll();
    }
    return stack.peek();
}