剑指offer——33.丑数

题目描述

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

思路：
一个数组，三个队列（这个队列不是真的队列，就是用来计算数据的）
数组：最终的结果数组
三个队列：分别是2,3,5三个丑数对应的队列，用来保存当前元素*对应丑数的结果。
数组第一个是1，三个队列分别对此数据进行运算，得到2,3,5.比较最小的放入结果数组。
此时数组是1,2，之前的2对数组的第一个操作过了，因此2指向数组下一个的数字2.因此三个队列的数据是4,3,5.依旧最小的放入结果数组。
此时数组是1,2,3,之前的3操作了第一个数字，因此指向下一个数字2，因此三个队列的数据是4,6,5.最小的放入结果数组...
......

最终数组从下标0开始—对应的数字1 第N个就是数组的第N-1的值，即为所求。

代码：

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