剑指offer--丑数

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

思路：
做到空间复杂度是O(1)，从小找起，因为丑数的因数总是为2，3，5，丑数总是由丑数×2、×3、×5构成。定义每次的坐标，想象有三个队列，每次都取当时最小的×2，×3，×5的数。对应的队列下标增加。因为共用同一个队列，那么，就定义一个队列就可以了。

代码：

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if( index <= 0 ) return 0;
        int[] ret = new int[index];
        int count = 0;
        ret[count] = 1;
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        while( count < index-1 ){
            int tmp = Math.min( ret[i2]*2, Math.min(ret[i3]*3, ret[i5]*5));
            if( tmp == ret[i2]*2 ) i2++;
            if( tmp == ret[i3]*3 ) i3++;
            if( tmp == ret[i5]*5 ) i5++;
            ret[++count] = tmp;
        }
        return ret[index-1];
    }
}