丑数

丑数

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

输入格式

输入一个整数n,n表示按从小到大的顺序的第 n 个丑数。 

输出格式

第n个丑数是:...

输入样例

请输入n的值：10

输出样例

第10个丑数是12

解题思路

为了找到第n个丑数，我们可以使用动态规划的方法。我们创建一个数组dp，其中dp[i]表示第i个丑数。我们使用三个指针i2、i3和i5分别跟踪当前最小丑数的下一个丑数的位置，它们分别对应乘以2、3和5的操作。初始时，dp[0]被设置为1，因为1是所有丑数的起点，i2、i3和i5都指向0。 每次迭代中，我们计算下一个丑数为min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)，并更新dp[i]。然后，根据dp[i]的值更新指针i2、i3和i5。重复这个过程，直到dp[n-1]被计算出来，即为第n个丑数。

代码实现

//丑数
import java.util.Scanner;

public class UglyNumber {
    public static int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0; // 分别指向下一个乘以2、3、5的丑数的位置

        for (int i = 1; i < n; i++) {
            // 计算下一个丑数
            dp[i] = Math.min(Math.min(dp[i2] * 2, dp[i3] * 3), dp[i5] * 5);
            
            // 更新指针
            if (dp[i] == dp[i2] * 2) i2++;
            if (dp[i] == dp[i3] * 3) i3++;
            if (dp[i] == dp[i5] * 5) i5++;
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入n的值：");
        int n = scanner.nextInt();
        scanner.close();
        
        int result = nthUglyNumber(n);
        System.out.println("第 " + n + " 个丑数是：" + result);
    }
}