题解 | #丑数#

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0) return 0;
        int dp2 = 1,dp3 = 1, dp5 = 1;
        // 定义数组 dp，其中 dp[i] 表示第 i 个丑数，第 n 个丑数即为 dp[n]。
        int[] dp = new int[index+1];
        dp[1] = 1;
        for (int i = 2; i <= index; i++) {
            // dp[dpi] 一定是丑数，那么numi也一定是丑数；并且numi > dp[i-1]
            int num2 = dp[dp2]*2;
            int num3 = dp[dp3]*3;
            int num5 = dp[dp5]*5;
            dp[i] = Math.min(num2,Math.min(num3,num5));

            // 判断相等就说明使用到了，故而需要向后移1位
            // 三个if都要判断，这样可以去重 
            //     比如 dp2:3,dp3:2,dp5:2 => dp2:4,dp3:3,dp5:2 , dp[6]:6 = num2=num3

            if (dp[i] == num2) {
                dp2++;
            }
            if (dp[i] == num3) {
                dp3++;
            }
            if (dp[i] == num5) {
                dp5++;
            }
//              System.out.println("dp2:" + dp2 + ",dp3:" + dp3 + ",dp5:" + dp5);
//              System.out.println("dp["+i+"]:" + dp[i]);
        }
        return dp[index];
    }
}