用Java编写求第n个丑数的算法

以下是使用Java编写的算法，用于找到按从小到大顺序的第n个丑数： ```java public class UglyNumber { public static int getNthUglyNumber(int n) { int[] uglyNumbers = new int[n]; uglyNumbers[0] = 1; int index2 = 0, index3 = 0, index5 = 0; int factor2 = 2, factor3 = 3, factor5 = 5; for (int i = 1; i < n; i++) { int min = Math.min(Math.min(factor2, factor3), factor5); uglyNumbers[i] = min; if (min == factor2) { index2++; factor2 = uglyNumbers[index2] * 2; } if (min == factor3) { index3++; factor3 = uglyNumbers[index3] * 3; } if (min == factor5) { index5++; factor5 = uglyNumbers[index5] * 5; } } return uglyNumbers[n - 1]; } public static void main(String[] args) { int n = 10; int nthUglyNumber = getNthUglyNumber(n); System.out.println("第 " + n + " 个丑数是：" + nthUglyNumber); } } ``` 这个算法使用了动态规划的思想。我们创建一个数组 `uglyNumbers` 来存储丑数，初始时将第一个丑数设置为1。然后，我们使用三个指针 `index2`、`index3` 和 `index5` 分别指向数组中下一个可能的丑数，初始时都指向第一个丑数。同时，我们维护三个因子 `factor2`、`factor3` 和 `factor5`，分别表示下一个可能的丑数是当前丑数乘以对应的因子。 接下来，我们从第二个丑数开始，通过比较三个因子的值，选择最小的值作为下一个丑数，并更新对应的指针和因子。重复这个过程，直到找到第n个丑数。 在上面的示例中，我们找到了第10个丑数，并将结果打印出来。你可以根据需要修改变量 `n` 的值来找到其他位置的丑数。