题解 | 寻找丑数

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        // 每一个丑数都是由前面的丑数*2*3*5得来的
        int[] dp = new int[n];
        dp[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        for(int i = 1; i < n; i++){
            int ugly2 = dp[index2] * 2;
            int ugly3 = dp[index3] * 3;
            int ugly5 = dp[index5] * 5;

            dp[i] = Math.min(Math.min(ugly2,ugly3),ugly5);
            if(dp[i] == ugly2){
                index2++;
            }
            if(dp[i] == ugly3){
                index3++;
            }
            if(dp[i] == ugly5){
                index5++;
            }
        }
        System.out.println(dp[n - 1]);
    }
}