JZ33-丑数

class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 6) {
            return index;
        }
        int i2 = 0, i3 = 0, i5 = 0; //初始化三个指向三个潜在成为最小丑数的位置  用于 * 2 3 5 来选择
        int[] dp = new int[index];
        dp[0] = 1;

        for (int i = 1; i < index; i++) {
            int next2 = dp[i2] * 2;
            int next3 = dp[i3] * 3;
            int next5 = dp[i5] * 5;
            dp[i] = Math.min(next2, Math.min(next3, next5));

            if (dp[i] == next2)
                i2++;           //为了防止重复需要三个if都能够走到。
            if (dp[i] == next3)
                i3++;  //丑数*丑数  下一个3的倍数的丑数只能是第二小的丑数*3（因为第一个小的丑数已经乘过了）
            if (dp[i] == next5)
                i5++;
        }
        return dp[index - 1];
    }
}