题解 | #丑数#

33、丑数

解题思路：

我们先看到题目，把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。

有了上面的定义我们就可以知道，丑数的形式就是2^x3^y5^z
所以我们可以定义一个数组res，存储第n个丑数。
因为我们要将丑数按从小到大的顺序排序，所以我们就得将对应的丑数放在对应的下标位置，小的放前面。
因为最小的丑数就是1，所以我们初始化res[0]=1，那么接下来的一个丑数是什么呢？我们自己知道是2。
但是我们能不能有一个格式，去将得到接下来的丑数是谁呢？
这个时候上面我们的出来的丑数的格式就起作用了，丑数的形式无非就是这样2^x3^y5^z
所以我们就将res[n]去乘以 2、3、5，然后比较出最小的那个，就是我们当前的下一个丑数了。

代码：

public int GetUglyNumber_Solution(int index) {
        //1 2 3 4 5 6 8
        if(index <= 6)
            return index;   // 加快程序输出

        // 三个变量 后面有大作用！
        int i2 = 0,i3 = 0,i5 = 0;
        int[] res = new int[index];
        res[0] = 1;  // 第一个丑数为 1

        for(int i = 1; i < index; i++){
            // 得到下一个丑数，三者中最小的
            res[i] = Math.min(res[i2]*2,Math.min(res[i3]*3,res[i5]*5));
             /*第一次是 2、3、5比较，得到最小的是2*/
            /*第二次是 4、3、5比较，为什么是4了呢？因为上次2已经乘了一次了，所以接下去可以放的丑数在4、3、5之间*/
            // 所以开头的三个指针就是来标记2 3 5 乘的次数的 
            if(res[i] == res[i2]*2)
                i2++;
            if(res[i] == res[i3]*3)
                i3++;
            if(res[i] == res[i5]*5)
                i5++;
        }
        return res[index-1];
    }

上面说的可能有点小拗口，但是只要按照代码然后看上面的动图自己动手去理解，就可以很快的搞懂它了~

复杂度分析：

• 时间复杂度：O(n)。取决于index值，循环中计算的次数为index。
• 空间复杂度：O(n)。取决于数组res的大小。