剑指Offer——丑数 Java

题目描述

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

解题思路（抄题 -.-|||）

根据丑数的定义，一个丑数应该是另外一个丑数乘以2,3,5的结果（1除外，乘1还是自身）。

我们创建一个数组，确保里面的丑数是从小到大排好序的，每个丑数都是有前面的丑数乘以2或3或5得到。

假设我们已有的最大丑数为M，那么M的下一个丑数肯定是由前面的某一个丑数乘以2 或者 乘以3 或者 乘以5得到

以乘以2为例，如果将前M个丑数都乘以2 ，那么必然能得到 一部分丑数 是小于M （前M个里面），以及一部分大于等于M的丑数，类似的，前M个丑数乘以3 或者 5 都能得到类似的结果，而我们只关心M的下一个丑数，也就是说再大于M的丑数里面 我们找那个最小的。

这也是为什么确保数组有序，这样我们乘2得到的结果也是有序的，乘3得到的也是有序的 ....

事实上并不需要每个小于M的丑数都乘以2，肯定存在某一个丑数（前M个里面的）T2，比他小的乘以2都小于M，比他大的乘以2 都会太大。

而 T2*2 可能正好 大于等于M，类似的 也有T3 T5，我们需要找到的是

min(T2*2,T3*3,T5*5) 得到的就是 恰好M的下一个丑数。

题解

public int GetUglyNumber_Solution(int index) {
    if (index <= 0) return 0;
    int mem[] = new int[index];
    mem[0] = 1;
    int t2=0,t3=0,t5=0;
    for (int i = 1; i < index; i++) {
        mem[i] = min(t2*2,t3*3,t5*5);
        if (t2*2 == mem[i]) t2++;
        if (t3*3 == mem[i]) t3++;
        if (t5*5 == mem[i]) t5++;
    }
    return mem[index-1];
}

public int min(int a,int b,int c){
    int min = a;
    if (b < min ){
        min = b;
    }
    if (c < min){
        min = c;
    }
    return min;
}