《剑指offer第二版》面试题49：丑数（Ugly Number

题目描述

• 题目描述：我们把只包含2，3，5的数称为丑数（ugly number），求从小到大的顺序的第1500个丑数。例如6，8是丑数，但14不是，因为它包含因子7。习惯上我们把1称为第一个丑数。

解题思路

1. 根据丑数的定义，丑数应该是丑数乘以2、3或者5的结果。
2. 可以创建一个数组A，数组里的数字是排好序的丑数。
3. 假设数组里最大的丑数是M，则接下的一个丑数则是之前的某个丑数乘以2、3或者5的结果。
4. 记录三个下标，K2，K3，K5，其中 A[K2]* 2刚好大于M, A[K3]* 3刚好大于M, A[K5]* 5也刚好大于M。
5. 则接下来的丑数是A[K2]* 2 、 A[K3]* 3 和 A[K5]* 5的最小值。同时更新K2，K3，K5的值。

代码

int getUglyNumber(int index){
    if (index <= 0) {
        return 0;
    }
    int[] uglys = new int[index];
    // 第一个丑数是1
    uglys[0] = 1;
    // 记录下一个丑数在数组里的下标
    int nextUglyIndex = 1;

    int uglyIndexMulti2 = 0;
    int uglyIndexMulti3 = 0;
    int uglyIndexMulti5 = 0;

    while (nextUglyIndex < index) {
        uglys[nextUglyIndex] = min(uglys[uglyIndexMulti2] * 2,
                                    uglys[uglyIndexMulti3] * 3,
                                    uglys[uglyIndexMulti5] * 5);
        while (uglys[uglyIndexMulti2] * 2 <= uglys[nextUglyIndex]) {
            uglyIndexMulti2++;
        }
        while (uglys[uglyIndexMulti3] * 3 <= uglys[nextUglyIndex]) {
            uglyIndexMulti3++;
        }
        while (uglys[uglyIndexMulti5] * 5 <= uglys[nextUglyIndex]) {
            uglyIndexMulti5++;
        }
        nextUglyIndex ++;
    }
    return uglys[index - 1];
}

int min(int a, int b, int c) {
    return Math.min(Math.min(a,b),c);
}